Given two integers, x and n, where n is non-negative, efficiently compute the power function pow(x, n).

For example,

pow(-2, 10) = 1024
pow(-3, 4) = 81
pow(5, 0) = 1
pow(-2, 3) = -8

Practice this problem

1. Naive Iterative Solution

A simple solution to calculate pow(x, n) would multiply x exactly n times. We can do that by using a simple for loop. This is demonstrated below in C, Java, and Python:

C


Download  Run Code

Output:

pow(-2, 10) = 1024

Java


Download  Run Code

Output:

pow(-2, 10) = 1024

Python


Download  Run Code

Output:

pow(-2, 10) = 1024

The time complexity of the above solution is O(n).

2. Using Divide and Conquer

We can recursively define the problem as:

power(x, n) = power(x, n / 2) × power(x, n / 2);        // otherwise, n is even
power(x, n) = x × power(x, n / 2) × power(x, n / 2);    // if n is odd

Following is the C, Java, and Python program that demonstrates it:

C


Download  Run Code

Output:

pow(-2, 10) = 1024

Java


Download  Run Code

Output:

pow(-2, 10) = 1024

Python


Download  Run Code

Output:

pow(-2, 10) = 1024

The time complexity of the above solution is O(n).

3. Optimized Divide and Conquer Solution

The problem with the above solution is that 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.

The implementation can be seen below in C, Java, and Python:

C


Download  Run Code

Output:

pow(-2, 10) = 1024

Java


Download  Run Code

Output:

pow(-2, 10) = 1024

Python


Download  Run Code

Output:

pow(-2, 10) = 1024

The time complexity of the above solution is O(log(n)).

4. Using Low-Level Programming (Binary Operators)

We can also use binary operators to compute pow(x, n) in O(log(n)) time.

C


Download  Run Code

Output:

pow(-2, 10) = 1024

Java


Download  Run Code

Output:

pow(-2, 10) = 1024

Python


Download  Run Code

Output:

pow(-2, 10) = 1024

The time complexity of the above solution is O(log(n)).