medium
Pow(x, n)
Implement a function computing x raised to the integer power n, where n may be negative or zero, using far fewer than |n| multiplications.
Constraints
- -100 < x < 100
- -2^31 ≤ n ≤ 2^31 - 1
- The result fits in a double
Examples
in: x = 2, n = 10
out: 1024
in: x = 2, n = -2
out: 0.25
Recognition clues
- Exponent up to 2^31 rules out a linear loop
- x^n = (x^(n/2))^2, times x when n is odd
- Halve the exponent each step
Pattern
Math & Number TheoryAn answer "modulo a prime" says intermediate values overflow and you must reduce at every step, and that division becomes multiplication by a modular inverse. Bounds like 10^18 rule out iteration and point to O(log n) exponentiation or Euclid; "all primes up to n" is a sieve.
Solution
Handle a negative exponent by inverting x and negating n (careful with -2^31). Then iterate over the bits of n: keep a running base that is squared each step, and multiply it into the result whenever the current lowest bit of n is 1. Each iteration halves n, so about 31 multiplications suffice for any 32-bit exponent.
time O(log n)space O(1)
Alternative approaches
- Recursive halving is the same idea with O(log n) stack. Under a modulus the identical loop gives modular exponentiation.
Code it yourself
Solve in
Hints: