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