Problem Statement: Given a double x and integer n, calculate x raised to power n. Basically Implement pow(x, n).
Examples:
Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Explanation: You need to calculate 2.00000 raised to 10 which gives ans 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Explanation: You need to calculate 2.10000 raised to 3 which gives ans 9.26100
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Brute force approach
Approach: Looping from 1 to n and keeping a ans(double) variable. Now every time your loop runs, multiply x with ans. At last, we will return the ans.
Now if n is negative we must check if n is negative, if it is negative divide 1 by the and.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
double myPow(double x, int n) {
double ans = 1.0;
for (int i = 0; i < n; i++) {
ans = ans * x;
}
return ans;
}
int main()
{
cout<<myPow(2,10)<<endl;
}
Output: 1024
Time Complexity: O(N)
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main{
public static double myPow(double x, int n) {
double ans = 1.0;
for(int i = 0; i<n; i++){
ans = ans * x;
}
return ans;
}
public static void main(String args[])
{
System.out.println(myPow(2,10));
}
}
Output: 1024.0
Time Complexity: O(N)
Space Complexity: O(1)
Python Code
def myPow(x: float, n: int) -> float:
ans = 1.0
for i in range(n):
ans = ans * x
return ans
if __name__ == "__main__":
print(myPow(2, 10))
Output: 1024.0
Time Complexity: O(N)
Space Complexity: O(1)
Solution 2: Using Binary Exponentiation
Approach: Initialize ans as 1.0 and store a duplicate copy of n i.e nn using to avoid overflow
Check if nn is a negative number, in that case, make it a positive number.
Keep on iterating until nn is greater than zero, now if nn is an odd power then multiply x with ans ans reduce nn by 1. Else multiply x with itself and divide nn by two.
Now after the entire binary exponentiation is complete and nn becomes zero, check if n is a negative value we know the answer will be 1 by and.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
double myPow(double x, int n) {
double ans = 1.0;
long long nn = n;
if (nn < 0) nn = -1 * nn;
while (nn) {
if (nn % 2) {
ans = ans * x;
nn = nn - 1;
} else {
x = x * x;
nn = nn / 2;
}
}
if (n < 0) ans = (double)(1.0) / (double)(ans);
return ans;
}
int main() {
cout << myPow(2, 10) << endl;
}
Output: 1024
Time Complexity: O(log n)
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main{
public static double myPow(double x, int n) {
double ans = 1.0;
long nn = n;
if (nn < 0) nn = -1 * nn;
while (nn > 0) {
if (nn % 2 == 1) {
ans = ans * x;
nn = nn - 1;
} else {
x = x * x;
nn = nn / 2;
}
}
if (n < 0) ans = (double)(1.0) / (double)(ans);
return ans;
}
public static void main(String args[])
{
System.out.println(myPow(2,10));
}
}
Output: 1024.0
Time Complexity: O(log n)
Space Complexity: O(1)
Python Code
def myPow(x: float, n: int) -> float:
ans = 1.0
nn = n
if nn < 0:
nn = -1 * nn
while nn:
if nn % 2:
ans = ans * x
nn = nn - 1
else:
x = x * x
nn = nn // 2
if n < 0:
ans = 1.0 / ans
return ans
if __name__ == "__main__":
print(myPow(2, 10))
Output: 1024.0
Time Complexity: O(log n)
Space Complexity: O(1)
Special thanks to Rushikesh Adhav and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article