Pow(x, n)
Medium· fast exponentiation
Problem
Compute x raised to the integer power n, where n may be negative or very large in magnitude. Do it faster than multiplying x by itself n times.
Examples
Input: x = 2.0, n = 10
Output: 1024.0
Input: x = 2.0, n = -2
Output: 0.25
Constraints
- • -100.0 < x < 100.0
- • -2^31 <= n <= 2^31 - 1
- • x is non-zero or n > 0
Hints & approach
Hint 1
x^n = (x^(n/2))² when n is even.
Hint 2
When n is odd, pull out one extra factor of x.
Hint 3
For negative n, compute with 1/x and -n (watch for overflow when negating the minimum int).
Approachtry the hints first
Use exponentiation by squaring. If n is negative, replace x with 1/x and n with -n, using a wider integer type to avoid overflow. Then loop while n > 0: if the lowest bit of n is set, multiply the result by x; square x and halve n. Each step consumes one bit of the exponent.
Time O(log n) · Space O(1)