x raised to the power n efficiently.
Problem
Implementpow(x, n), which calculates xn. The value of n can be negative, so for a negative exponent, the result is calculated as 1 / x-n.
Example(s)
Example 1
Input
x = 2.00000
n = 10Output
1024.00000Example 2
Input
x = 2.10000
n = 3Output
9.26100Solution
This problem uses Binary Exponentiation. Instead of multiplyingx repeatedly, square the base and halve the exponent at every step. When the exponent is odd, multiply the result by the current base.
A
long is used for the exponent because Integer.MIN_VALUE cannot be safely negated as an int.
class Solution {
public double myPow(double x, int n) {
long exponent = n;
if (exponent < 0) {
x = 1 / x;
exponent = -exponent;
}
double result = 1.0;
while (exponent > 0) {
if (exponent % 2 == 1) {
result *= x;
}
x *= x;
exponent /= 2;
}
return result;
}
}