Example 1: Input: 2.00000, 10 Output: 1024.00000

**Achieve it within O(log n)**

This problem can be solved in 4 different ways:

- Recursive
- Iterative
- Divide and Conquer
- Bit Manipulation

We shall look at the first 3 methods.

**So let us understand how pow(x ^ n) means.**

It means, multiplies “x” with “n” “x’s”.

2 ^3 = 2 * 2 * 2 = 8

or multiply (n-1) times.

This can be achieved easily by using for loop.

for ( i = 1; i <= n; i ++) result = result * x;

This solution will give time complexity of **O(n)**.

But according to the question we need to achieve it with **O(log n)**.

## 1. Using Recursion

So this can be achieved by using the below formula:

For “x^n” If n is even then calculate (pow (x ^ (n/2)) * pow(x ^(n/2))). If n is odd then calculate (x * pow(x ^ n/2)). This is because, in the odd case, we return 1. In the below example, in pass 4, I have explained the concept.

Example:

pow (2 ^ 8)

Pass 1: In Even case x = 2 n = 8 x * x = 4 n/2 = 4

Pass 2: In Even case x = 4 n = 4 x * x = 16 n/2 = 2

Pass 3: In Even case x = 16 n = 2 x * x = 256 n/2 = 1

Pass 4: In odd case x = 256 n = 1 x * x = 65536 n/2 = 0

As n is 0. The recursion function will return 1. Hence the final result will be 256.

The result is 256

## 2. Divide and Conquer

In this solution, we follow the same above procedure and we do it iteratively instead of recursively.

## Solution in C++

#include<iostream> using namespace std; double get_pow_recursive(double x, int n) { // base case if(n == 0) return 1; // check if n is negative if(n<0) { n = -n; x = 1/x; } // check if n is even or odd if(n%2 == 0) { return get_pow_recursive(x*x, n/2); } else { return x*get_pow_recursive(x*x, n/2); } } double get_pow_divide_conquer(double x, int n) { double result =1; while(n != 0) { if(n%2 == 0) { x = x*x; n /= 2; } else { if(n>0) { result *= x; n--; } else { result/=x; n++; } } } return result; } int main() { int x = 2; int n = 8; double result = 0; //result = get_pow_recursive(x, n); result = get_pow_divide_conquer(x, n); cout<<"The result is "<<result<<endl; return 0; }

Output:

The result is 256