The problem
Compute x raised to the power n — x multiplied by itself n times — for a real x and a whole number n that may be negative.
Examples
01
- Input
x = 2, n = 10
- Output
1024
02
- Input
x = 2.1, n = 3
- Output
9.261
03
- Input
x = 2, n = -2
- Output
0.25
Constraints
- −100.0 < x < 100.0
- −2³¹ ≤ n ≤ 2³¹ − 1
- x is not 0 when n ≤ 0.
- −10⁴ ≤ xⁿ ≤ 10⁴
The idea
Multiplying n times is too slow for n near two billion. Instead, write n in binary: 13 is 8 + 4 + 1, so x¹³ = x⁸ · x⁴ · x¹. And x, x², x⁴, x⁸ each come from squaring the one before.
So walk through n’s bits from the lowest: whenever a bit is 1, multiply the current power of x into the result; then square x and move to the next bit. That takes about log₂ n steps — 31 at most. A negative n means x⁻ⁿ = (1 ÷ x)ⁿ; turning −2³¹ positive needs a 64-bit integer, since 2³¹ does not fit in 32 bits.
- Time
- O(log n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def myPow(self, x: float, n: int) -> float: if n < 0: x, n = 1 / x, -n # x^-n = (1/x)^n # Square-and-multiply: read n in binary. x, x², x⁴, x⁸… are one squaring apart, # and x^n is the product of those whose bit in n is 1. result = 1.0 while n: if n & 1: result *= x x *= x n >>= 1 return result