Implement myPow(x, n), which returns x raised to the integer power n. The exponent can be negative, and it can be as large as about two billion in absolute value, so multiplying x by itself n times is too slow.
2^-2 = 1 / 2^2 = 1 / 4- -100.0 < x < 100.0
- -2^31 <= n <= 2^31 - 1
- x is not zero when n is negative
- Answers are compared with a small tolerance
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force multiplies x by itself |n| times: O(n), which is two billion steps in the worst case. Fast power (binary exponentiation) uses the bits of n: write n in binary, and x^n is the product of x^(2^k) for every set bit k. Loop while n > 0: if the lowest bit is 1, multiply the result by the current base; then square the base and shift n right. That takes O(log n) steps. A negative exponent becomes positive by using 1/x as the base.
Algorithm
- Copy
ninto a 64-bit variablee. Ife < 0, setx = 1 / xande = -e. - Set
res = 1.0. - While
e > 0: ifeis odd,res *= x; thenx *= xande >>= 1. - Return
res.
O(log |n|)Space: O(1)n = -2147483648: in Java and C++, -n is still negative in a 32-bit int, so the loop breaks. Always widen to long / long long first.class Solution: def myPow(self, x: float, n: int) -> float: e = n if e < 0: x = 1 / x e = -e res = 1.0 while e > 0: if e & 1: # this bit of e is set res *= x x *= x # x, x^2, x^4, x^8, ... e >>= 1 return res