C++ Program To Calculate the Power of a Number
Write a C++ program for a 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 : 8Input : x = 7, n = 2
Output : 49
Program to calculate pow(x, n) using Naive Approach:
A simple solution to calculate pow(x, n) would multiply x exactly n times. We can do that by using a simple for loop
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Naive iterative solution to calculate pow(x, n) long power( int x, unsigned n) { // Initialize result to 1 long long pow = 1; // Multiply x for n times for ( int i = 0; i < n; i++) { pow = pow * x; } return pow ; } // Driver code int main( void ) { int x = 2; unsigned n = 3; // Function call int result = power(x, n); cout << result << endl; return 0; } |
8
- Time Complexity: O(n)
- Auxiliary Space: O(1)
pow(x, n) using recursion:
We can use the same approach as above but instead of an iterative loop, we can use recursion for the purpose.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int power( int x, int n) { // If x^0 return 1 if (n == 0) return 1; // If we need to find of 0^y if (x == 0) return 0; // For all other cases return x * power(x, n - 1); } // Driver Code int main() { int x = 2; int n = 3; // Function call cout << (power(x, n)); } // This code is contributed by Aditya Kumar (adityakumar129) |
8
- Time Complexity: O(n)
- Auxiliary Space: O(n) n is the size of the recursion stack
Program to calculate pow(x, n) using Divide and Conqueror approach:
To solve the problem follow the below idea:
There is a problem with the above solution, the same subproblem is computed twice for each recursive call. We can optimize the above function by computing the solution of the subproblem once only.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // 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; } /*Driver code */ int main() { int x = 2; // Base unsigned int y = 3; // Exponent int result = power(x, y); std::cout << result << std::endl; return 0; } |
8
Time Complexity: O(log n)
Auxiliary Space: O(log n), for recursive call stack
Extend the pow function to work for negative n and float x:
Below is the implementation of the above approach:
C++
/* 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; // Function call cout << power(x, y); return 0; } // This is code is contributed // by rathbhupendra |
0.125
Time Complexity: O(log |n|)
Auxiliary Space: O(log |n|) , for recursive call stack
Program to calculate pow(x,n) using inbuilt power function:
To solve the problem follow the below idea:
We can use inbuilt power function pow(x, n) to calculate xn
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int power( int x, int n) { // return type of pow() // function is double return ( int ) pow (x, n); } // Driver Code int main() { int x = 2; int n = 3; // Function call cout << (power(x, n)); } // This code is contributed by hemantraj712. |
8
Time Complexity: O(log n)
Auxiliary Space: O(1), for recursive call stack
Program to calculate pow(x,n) using Binary operators:
Some important concepts related to this approach:
- Every number can be written as the sum of powers of 2
- We can traverse through all the bits of a number from LSB to MSB in O(log n) time.
Illustration:
3^10 = 3^8 * 3^2. (10 in binary can be represented as 1010, where from the left side the first 1 represents 3^2 and the second 1 represents 3^8)
3^19 = 3^16 * 3^2 * 3. (19 in binary can be represented as 10011, where from the left side the first 1 represents 3^1 and second 1 represents 3^2 and the third one represents 3^16)
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <iostream> using namespace std; int power( int x, int n) { int result = 1; while (n > 0) { if (n & 1 == 1) // y is odd { result = result * x; } x = x * x; n = n >> 1; // y=y/2; } return result; } // Driver Code int main() { int x = 2; int n = 3; // Function call cout << (power(x, n)); return 0; } // This code is contributed bySuruchi Kumari |
8
Time Complexity: O(log n)
Auxiliary Space: O(1)
Program to calculate pow(x,n) using math.log2() and ** operator:
Here, we can use the math.log2() in combination with the operator “**” to calculate the power of a number.
Below is the implementation of the above approach.
C++
#include <cmath> #include <iostream> using namespace std; int calculatePower( int a, int n) { return round( pow (2, (log2(a) * n))); } int main() { int a = 2; int n = 3; cout << calculatePower(a, n) << endl; return 0; } |
8
Time Complexity: O(1)
Auxiliary Space: O(1)
Please refer complete article on Write program to calculate pow(x, n) for more details!
Contact Us