Pow(x, n)
Medium Fast exponentiation
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Compute x raised to an integer power n, where n can be negative and as large as 2^31 in size.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: x to the power n where n can be about ±2 billion.
Why this works: x^13 = x^8 · x^4 · x^1 (13 is 1101 in binary). Squaring x each step gives x, x², x⁴, x⁸; multiply in the ones whose bit is set. That's about 31 steps instead of 2 billion.
Example: x = 2, n = 10 (binary 1010)
bit 0 = 0: base 2 → 4bit 1 = 1: result 4, base 16bit 2 = 0: base 256bit 3 = 1: result 4·256 = 1024
✦Hints open one at a time
↗Approach
Binary exponentiation: while the exponent is positive, if its lowest bit is 1 multiply the answer by the base; then square the base and shift the exponent right. That's O(log n) multiplications.
</>Solution (Java)
class Solution {
public double myPow(double x, int n) {
long e = n; // long avoids overflow for Integer.MIN_VALUE
if (e < 0) {
x = 1 / x;
e = -e;
}
double result = 1;
while (e > 0) {
if ((e & 1) == 1) result *= x; // this bit of the exponent is set
x *= x;
e >>= 1;
}
return result;
}
}!Common mistake
Writing n = -n with an int when n == Integer.MIN_VALUE — it stays negative.
- Time: O(log n).
- Space: O(1).
