Problem
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).
Examples
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/2^2 = 1/4 = 0.25
Solution
Method 1 - Normal Multiplication
Code
Java
public double myPow(double x, int n) {
double ans = 1;
for(int i = 0; i < n; i++){
ans = ans * x;
}
return ans;
}
Method 2 - Divide and Conquer
When we have an even exponent, for eg. 2^10, we have ans = 2^5 * 2^5. Likewise, when we have odd we have 2^11 = 2 * 2^5 * 2^5. There is 1 minor change we can do, using a^2n = (a^2)^n = (a*a)^n.
Code
Java
public double pow(double x, int n) {
if(n == 0) {return 1;}
if (x == 0) {return 0;}
if(n<0){
n = -n;
x = 1/x;
}
int ans = pow(x*x, n/2);
return (n%2 == 0) ? ans : x*ans;
}