Write program to calculate pow(x, n)

Given two integers x and n , write a function to compute x n . We may assume that x and n are small and overflow doesn’t happen.

Examples :

Input : x = 2, n = 3
Output : 8

Input : x = 7, n = 2
Output : 49

Naive Approach: To solve the problem follow the below idea:

A simple solution to calculate pow(x, n) would multiply x exactly n times. We can do that by using a simple for loop

Below is the implementation of the above approach:

                                                       Java

                                                     Python

Time Complexity: O(n)
Auxiliary Space: O(1)

pow(x, n) using recursion:

We can use the same approach as above but instead of an iterative loop, we can use recursion for the purpose.

                                           Python

Time Complexity: O(n)
Auxiliary Space: O(n) n is the size of the recursion stack

Program to calculate pow(x, n) using Divide and Conqueror approach:

To solve the problem follow the below idea:

The problem can be recursively defined by:

• power(x, n) = power(x, n / 2) * power(x, n / 2); // if n is even
• power(x, n) = x * power(x, n / 2) * power(x, n / 2); // if n is odd

Below is the implementation of the above approach:

                                                           Java

Time Complexity: O(2^y) , due to redundant calculations from multiple recursive calls.
Auxiliary Space: O(log y)

An Optimized Divide and Conquer Solution:

To solve the problem follow the below idea:

There is a problem with the above solution, the same subproblem is computed twice for each recursive call. We can optimize the above function by computing the solution of the subproblem once only.

Below is the implementation of the above approach:

                                      Java

Time Complexity: O(log n)
Auxiliary Space: O(log n), for recursive call stack

Extend the pow function to work for negative n and float x:

Below is the implementation of the above approach:

                                                                  Java

       Rust

0.125

Time Complexity: O(log |n|)
Auxiliary Space: O(log |n|) , for recursive call stack

Program to calculate pow(x,n) using inbuilt power function:

To solve the problem follow the below idea:

We can use inbuilt power function pow(x, n) to calculate x n

Below is the implementation of the above approach:

                          Python

                                     JavaScript

Time Complexity: O(log n)
Auxiliary Space: O(1), for recursive call stack

Program to calculate pow(x,n) using Binary operators:

To solve the problem follow the below idea:

• Every number can be written as the sum of powers of 2
• We can traverse through all the bits of a number from LSB to MSB in O(log n) time.

Illustration:

3^10 = 3^8 * 3^2. (10 in binary can be represented as 1010, where from the left side the first 1 represents 3^2 and the second 1 represents 3^8)

3^19 = 3^16 * 3^2 * 3. (19 in binary can be represented as 10011, where from the left side the first 1 represents 3^1 and second 1 represents 3^2 and the third one represents 3^16)

Below is the implementation of the above approach.

Time Complexity: O(log n)
Auxiliary Space: O(1)

Program to calculate pow(x,n) using Python ** operator:

To solve the problem follow the below idea:

In Python language, we can easily find power of a number using ** operator.

Below is the implementation of the above approach.

                                     Java

                                       Python

Time Complexity: O(log n)
Auxiliary Space: O(1)

Program to calculate pow(x,n) using Python numpy module:

We can install NumPy by running the following command:

pip install numpy

To solve the problem follow the below idea:

In Python language, we can easily find power of a number using the NumPy library’s “power” function. This function allows you to calculate the power of a number using a single line of code.

Below is the implementation of the above approach.

                          Java

Output

Program to calculate pow(x,n) using math.log2() and ** operator:

Here, we can use the math.log2() in combination with the operator “ ** ” to calculate the power of a number.

                                Java

                                      Python

                                       JavaScript

Program to calculate pow(x,n) using math.exp() function:

In math library, the math.exp() function in Python is used to calculate the value of the mathematical constant e (2.71828…) raised to a given power. It takes a single argument, which is the exponent to which the constant e should be raised, and returns the result as a float. Now, if we use combination of math.log() and math.exp() function, then we can find power of any number.

                                          Java

                                             Python

                                          JavaScript

Result: 8

Complexity Analysis:

Time Complexity: O(1), as both math.exp() and math.log() functions run on O(1) time complexity.
Auxiliary Space: O(1), as no extra space is used.

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Please Login to comment.

Similar Reads

Given an integer x and a positive number y, write a function that computes xy under following conditions. a) Time complexity of the function should be O(Log y) b) Extra Space is O(1) Examples: Input: x = 3, y = 5Output: 243Input: x = 2, y = 5Output: 32 We strongly recommend that you click here and practice it, before moving on to the solution.We ha

Given an integer n, calculate the square of a number without using *, / and pow(). Examples : Input: n = 5 Output: 25 Input: 7 Output: 49 Input: n = 12 Output: 144 A Simple Solution is to repeatedly add n to result. Below is the implementation of this idea. C/C++ Code // Simple solution to calculate square without // using * and pow() #include <

Size of a tree is the number of elements present in the tree. Size of the below tree is 5. Size() function recursively calculates the size of a tree. It works as follows:Size of a tree = Size of left subtree + 1 + Size of right subtree. Recommended PracticeSize of Binary TreeTry It!Algorithm: size(tree)1. If tree is empty then return 02. Else (a) G

When compiling a C program that uses the pow function, you might encounter the following error message: undefined reference to `pow'Why Does undefined reference to `pow' error OccursThe pow function is part of the math library in C, which is not linked by default when you compile your program. The math library (libm) contains mathematical functions

To delete a tree, we must traverse all the nodes of the tree and delete them one by one. So, which traversal we should use - inorder traversal, preorder traversal, or the postorder traversal? The answer is simple. We should use the postorder traversal because before deleting the parent node, we should delete its child nodes first.We can delete the

Asked by Anshya. Base 14: Decimal numbersBase 14 numbers0011223344556677889910A11B12C13D14D1 Below are the different ways to add base 14 numbers.Method 1 Thanks to Raj for suggesting this method. 1. Convert both i/p base 14 numbers to base 10. 2. Add numbers. 3. Convert the result back to base 14. Method 2 Just add the numbers in base 14 in the sam

Write a program to reverse the digits of an integer. Examples : Input : num = 12345 Output: 54321 Input : num = 876 Output: 678Flowchart: ITERATIVE WAY Algorithm: Input: num (1) Initialize rev_num = 0 (2) Loop while num > 0 (a) Multiply rev_num by 10 and add remainder of num divide by 10 to rev_num rev_num = rev_num*10 + num%10; (b) Divide num b

The atoi() function in C takes a string (which represents an integer) as an argument and returns its value of type int. So basically the function is used to convert a string argument to an integer. Syntax: int atoi(const char strn) Parameters: The function accepts one parameter strn which refers to the string argument that is needed to be converted

Given an unsigned integer, reverse all bits of it and return the number with reversed bits. Input : n = 1Output : 2147483648 Explanation : On a machine with size of unsigned bit as 32. Reverse of 0. 001 is 100. 0. Input : n = 2147483648Output : 1 Recommended PracticeReverse BitsTry It!Method1 - Simple: Loop through all the bits of an integer. I

Given an integer N, the task is to find the number of odd days in the years from 1 to N. Odd Days: Number of odd days refer to those days that are left in a certain year(s) when it's days gets converted into weeks. Say, an ordinary year has 365 days, that is 52 weeks and one odd day. This means, out of the 365 days in an ordinary year, 364 days wil

The Body Mass Index (BMI) or Quetelet index is a value derived from the mass (weight) and height of an individual, male or female. The BMI is defined as the body mass divided by the square of the body height and is universally expressed in units of kg/m2, resulting from the mass in kilograms and height in meters. The formula is: BMI = (mass or weig

Given the current date and birth date, find the present age. Examples: Input : Birth date = 07/09/1996 Present date = 07/12/2017 Output : Present Age = Years: 21 Months: 3 Days: 0 t Age = Years: 7 Months: 11 Days: 21 While calculating the difference in two dates we need to just keep track of two conditions that will do. If the current date is less

A trapezium is a quadrilateral with at least one pair of parallel sides, other two sides may not be parallel. The parallel sides are called the bases of the trapezium and the other two sides are called it's legs. The perpendicular distance between parallel sides is called height of trapezium. Formula : Area of Trapezium : 0.5 * (a + b) * h Perimete

A Tetrahedron is simply a pyramid with a triangular base. It is a solid object with four triangular faces, three on the sides or lateral faces, one on the bottom or the base and four vertices or corners. If the faces are all congruent equilateral triangles, then the tetrahedron is called regular. The area of Tetrahedron can be found by using the fo

An equilateral triangle is a triangle in which all three sides and angles are equal. All three internal angles of equilateral triangle measures 60 degree. If we know the length of each sides of equilateral triangle, then we can use below mentioned formula to calculate area of equilateral triangle.Area of Equilateral Triangle = (sqrt(3)/4) * a * a I

A regular octagon is a closed figure with sides of the same length and internal angles of the same size. It has eight lines of reflective symmetry and rotational symmetry of order 8. The internal angle at each vertex of a regular octagon is 135°. The central angle is 45°.Properties : Convex polygon, Equilateral polygon, Isogonal figure, Isotoxal fi

Given Original cost and Net price then calculate the percentage of GSTExamples: Input : Netprice = 120, original_cost = 100 Output : GST = 20% Input : Netprice = 105, original_cost = 100 Output : GST = 5% How to calculate GST GST ( Goods and Services Tax ) which is included in netprice of product for get GST % first need to calculate GST Amount by

Given the length of sides of an equilateral triangle. We need to write a program to find the area of Circumcircle of the given equilateral triangle.Examples: Input : side = 6 Output : Area of circumscribed circle is: 37.69 Input : side = 9 Output : Area of circumscribed circle is: 84.82 All three sides of equilateral triangle are of equal length an

Given the rank of a student and the total number of students appearing in an examination, the task is to find the percentile of the student. The percentile of a student is the % of the number of students having marks less than him/her. Examples: Input: Rank: 805, Total Number of Students Appeared: 97481 Output: 99.17 Explanation: ((97481 - 805) / 9

In mathematics, a triangular prism is a three-dimensional solid shape with two identical ends connected by equal parallel lines, and have 5 faces, 9 edges, and 6 vertices. where "b" is the length of the base, "h" is the height of the triangle, "s1, s2, s3" are the respective length of each side of the triangle, and H is the height of the prism (whi

Given the side of a square. The task is to find the area of an inscribed circle in a square.Examples: Input : a = 8 Output : Area of an inscribed circle: 50.24 Input : a = 12.04 Output : Area of an inscribed circle: 113.795 Given a square i.e. all sides of a square are of equal length and all four angles are 90 degrees. Below diagram depicts an ins

Given two coordinates (x1, y1, z1) and (x2, y2, z2) in 3 dimension. The task is to find the distance between them.Examples : Input: x1, y1, z1 = (2, -5, 7) x2, y2, z1 = (3, 4, 5) Output: 9.2736184955 Input: x1, y1, z1 = (0, 0, 0) x2, y2, z1 = (1, 1, 1) Output: 1.73205080757 Approach: The formula for distance between two points in 3 dimension i.e (x

Given the Cost Price(CP) and Selling Price(SP) of a product. The task is to Calculate the Profit or Loss.Examples: Input: CP = 1500, SP = 2000 Output: 500 Profit Input: CP = 3125, SP = 1125 Output: 2000 Loss Formula: Profit = (Selling Price - Cost Price) Loss = (Cost Price - Selling Price) Below is the required implementation: C/C++ Code // C++ cod

Given an array of amounts and time_period that represents the amount of money N persons invest and the time period for which they had invested. The task is to calculate the Profit ratio at the End.Examples: Input: n = 2, Amount1 = 7000, Time1 = 12 months Amount2 = 6000, Time2 = 6 months Output: 7 : 3Input: n = 3, Amount1 = 5000, Time1 = 6 months Am

Given an array of [Tex]N [/Tex]integers. The task is to find the Bitonicity of the given array.The Bitonicity of an array arr[] can be defined as: B[i] = 0, if i = 0. = B[i-1] + 1, if arr[i] > arr[i-1] = B[i-1] - 1, if arr[i] < arr[i-1] = B[i-1], if arr[i] = arr[i-1] Bitonicity will be last element of array B[]. Examples: Input : arr[] = 5 min read Program to calculate Root Mean Square

Given an array of N numbers. The task is to calculate the Root Mean Square(RMS) of the given numbers. Examples: Input: arr[] = <1, 2, 3, 4, 5>Output: 3.31662 Input: arr[] = Output: 7.34847 Approach: The Root Mean Square value of N numbers x1,x2,x3. xn can be given as, RMS method first calculates the square of each number and then

Given the number of vertices N of a graph. The task is to determine the Edge cover.Edge Cover: Minimum number of edges required to cover all vertex is known as Edge Cover. Examples: Input : N = 5 Output : 3 Input : N = 4 Output : 2 Example 1: For N = 5 vertices, Edge Cover is: 3 (Choosing the edges marked in Red, all of the vertices will get covere

Given side [Tex]S [/Tex]of a Decagon, the task is to find out the Perimeter of the Decagon.Explanation : In geometry, a decagon is a ten-sided polygon or 10-gon. A regular decagon has all sides of equal length and each internal angle will always be equal to 144 degrees. Examples: Input : S = 5 Output : The Perimeter of Decagon is : 50 Input : S = 8

Given the length of diagonals of a rhombus, d1 and d2. The task is to find the perimeter and the area of that rhombus. A rhombus is a polygon having 4 equal sides in which both the opposite sides are parallel, and opposite angles are equal. Examples: Input: d1 = 2 and d2 = 4 Output: The area of rhombus with diagonals 2 and 4 is 4. The perimeter of

Given the length of sides of an equilateral triangle, the task is to find the area and perimeter of Incircle of the given equilateral triangle. Examples: Input: side = 6 Output: Area = 9.4. Perimeter = 10.88 Input: side = 9 Output: Area = 21.21, Perimeter = 16.32 Properties of an Incircle are: The center of the Incircle is same as the center of the