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

Output:

pow(-2, 10) = 1024

## Java

Output:

pow(-2, 10) = 1024

## Python

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

Output:

pow(-2, 10) = 1024

## Java

Output:

pow(-2, 10) = 1024

## Python

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

Output:

pow(-2, 10) = 1024

## Java

Output:

pow(-2, 10) = 1024

## Python

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

Output:

pow(-2, 10) = 1024

## Java

Output:

pow(-2, 10) = 1024

## Python

Output:

pow(-2, 10) = 1024

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