Implement pow(x, n), which calculates x raised to the power n (x^n) in C++

Example 1:
Input: 2.00000, 10
Output: 1024.00000

Achieve it within O(log n)

This problem can be solved in 4 different ways:

1. Recursive
2. Iterative
3. Divide and Conquer
4. 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

List Of Tutorials available in this website: