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

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000

Explanation: 2-2 = 1/22 = 1/4 = 0.25

Achieve it with in O(long 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 first 3 methods.

So let us understand how pow(x ^ n) means.
It means, multiply “x” with “n” “x’s”.

2 ^3 = 2 * 2 * 2 = 8

Means, 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 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++

/*
* File     : pow_x_n.cpp
* Author   : ajay.thousand@gmail.com
* Copyright: @ prodevelopertutorial.com
*/


#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