Description
Compute x raised to signed 32-bit integer n. Negative powers return the reciprocal; assume x is nonzero whenever n is negative, and inputs obey the problem's finite-result constraints.
Solution
def my_pow(x, n):
if n < 0:
x, n = 1 / x, -n
result = 1.0
while n:
if n & 1:
result *= x
x *= x
n >>= 1
return resultExamples
Example 1
- Input
[2,10]- Output
1024
Ten factors of 2 produce 1024.
Example 2
- Input
[2,-2]- Output
0.25
The reciprocal of 2 squared is one quarter.
Example 3
- Input
[3,0]- Output
1
The zero exponent gives one.
Approach
Convert a negative exponent to a positive one while replacing the base by its reciprocal. Repeatedly square the base; multiply it into the result only when the current exponent bit is set.
Time & space
O(log(|n| + 1)) time and O(1) auxiliary space.