Write a program to calculate pow(x,n)

Hello Everyone,

Given two integers x and n, write a function to compute xn. We may assume that x and n are small and overflow doesn’t happen.

Examples :

Input : x = 2, n = 3 Output : 8 Input : x = 7, n = 2 Output : 49

Below solution divides the problem into subproblems of size y/2 and call the subproblems recursively.

// C++ program to calculate pow(x,n)
#include
using namespace std;
class gfg
{

/* Function to calculate x raised to the power y */
public:
int power(int x, unsigned int y)
{
if (y == 0)
return 1;
else if (y % 2 == 0)
return power(x, y / 2) * power(x, y / 2);
else
return x * power(x, y / 2) * power(x, y / 2);
}
};

/* Driver code */
int main()
{
gfg g;
int x = 2;
unsigned int y = 3;

cout << g.power(x, y);
return 0;

}

Output :

8
Time Complexity: O(n)
Space Complexity: O(1)

Algorithmic Paradigm: Divide and conquer.
Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

/* Function to calculate x raised to the power y in O(logn)*/
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return temp * temp;
else
return x * temp * temp;
}

Time Complexity of optimized solution: O(logn)

Let us extend the pow function to work for negative y and float x.

/* Extended version of power function
that can work for float x and negative y*/
#include <bits/stdc++.h>
using namespace std;

float power(float x, int y)
{
float temp;
if(y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return temp * temp;
else
{
if(y > 0)
return x * temp * temp;
else
return (temp * temp) / x;
}
}

// Driver Code
int main()
{
float x = 2;
int y = -3;
cout << power(x, y);
return 0;
}

Output :

0.125000
Time Complexity: O(log|n|)

Auxiliary Space: O(1)

Using recursion:

This approach is almost similar to iterative solution

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

int power(int x, int y)
{

// If x^0 return 1
if (y == 0)
    return 1;

// If we need to find of 0^y
if (x == 0)
    return 0;

// For all other cases
return x * power(x, y - 1);

}

// Driver Code
int main()
{
int x = 2;
int y = 3;

cout << (power(x, y));

}

Output:

8
Using Math.pow() function of java:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

int power(int x, int y)
{

// return type of pow()
// function is double
return (int)pow(x, y);

}

// Driver Code
int main()
{
int x = 2;
int y = 3;

cout << (power(x, y));

}

Output:

8