Pow(x, n)
Implement pow(x, n)xn-100.0 < x < 100.0-2^31 <= n <= 2^31 - 1xn > 0-10^410^4
The outputs below are written with five decimals, the way LeetCode prints them.
Example 1
Output: 1024.00000
Example 2
Output: 9.26100
Example 3
Output: 0.25000
Explanation: 2^-2 = 1 / 2^2 = 1 / 4.
How to Think About It
Step 1: Multiply n times
The obvious loop multiplies x|n|n
Step 2: Halve the exponent
Squaring doubles the exponent: x^10 = (x^2)^5x^5 = x × x^4int
Step 3: Read the steps from the binary form
Write 10 in binary as 1010, which means 10 = 8 + 2. So x^10 = x^8 × x^2xx^1, x^2, x^4, x^8, ...
Step 4: Negative exponents and the one value that breaks
x^-n = (1/x)^n1/xn = Integer.MIN_VALUEint-n
Copying nlonglongInteger.MIN_VALUE
Walkthrough
Example 1: x = 2n = 10x
| Pass | power | Lowest bit | x at start | result after | power after shift |
|---|---|---|---|---|---|
| 1 | 10 | 0 | 2 | 1 | 5 |
| 2 | 5 | 1 | 4 | 4 | 2 |
| 3 | 2 | 0 | 16 | 4 | 1 |
| 4 | 1 | 1 | 256 | 1024 | 0 |
The two 1 bits picked up 4 = 2^2 and 256 = 2^8, and 4 × 256 = 1024. Four passes replaced ten multiplications.
Java Solution
The method turns a negative exponent into a positive one, then walks the bits of the exponent from lowest to highest, squaring the base at each step.
- The
copy:long widens before negating, solong power = n is 2147483648 when-power isn .Integer.MIN_VALUE returns 0.0, because 2^-2147483648 is far below the smallest double.myPow(2.0, Integer.MIN_VALUE) - The odd bit:
tests the lowest bit. When it is set, the current square of(power & 1) == 1 is part of the answer and goes intox .result - Shifting:
drops the bit just used, andpower >>= 1 moves the base to the next power of two, so the two stay in step.x *= x - Small cases:
skips the loop and returns 1.0. A negative base keeps its sign for odd exponents:n = 0 is -8.0 andmyPow(-2.0, 3) is -1.0.myPow(-1.0, Integer.MAX_VALUE)
A common mistake is to negate the intn = -nMath.abs(n)Integer.MIN_VALUEmyPow(2.0, Integer.MIN_VALUE)
public class PowXN {
public double myPow(double x, int n) {
long power = n; // long, so -Integer.MIN_VALUE does not overflow
if (power < 0) {
x = 1 / x;
power = -power;
}
double result = 1.0;
while (power > 0) {
if ((power & 1) == 1) { // this bit of the exponent is set
result *= x;
}
x *= x; // x^1, x^2, x^4, x^8, ...
power >>= 1;
}
return result;
}
}
Complexity
- Time: O(log |n|). Each pass of the loop halves
, so the loop runs once per binary digit ofpower , at most 32 times even for|n| .Integer.MIN_VALUE - Space: O(1). The loop keeps only
,power and the squared base, and unlike a recursive version it uses no call stack.result
Each squaring roughly doubles the relative rounding error. For exponents up to 10^5, results stayed within 10^-11 of Math.pow