Calculate
-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]
Brute force
mult_res = 1
neg = False
if n < 0:
x = 1/x
neg = True
print(x)
n = abs(n)
for i in range(n):
mult_res = mult_res * x
return mult_res
We use mult_res to hold result. It inits at 1. This will help with the case when n = 0. We can just return mult_res directly.
Bugs
At the beginning, I didn’t take into the account where n could be negative. To fix it, I need to change x to 1/x when n < 0.
Binary search
The code above times out.
We used “stride” of size 1. But can we move in exponential step and scale back when we overstep?
If we have how would we get
. If x is even. Then
. This avoid the
multiplications we used in the first step.
When is odd,
will be
. So we need to multiple one
back.
.
So x^n = if n is even.
and x^n = * x if n is odd.
Let’s define a function that use this recursion:
def myPow(self, x, n):
def power(x, n):
if n == 0:
return 1
half = power(x , n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
if n < 0:
x = 1/x
n = -n
return power(x, n)
This recursive function first recursively calculate half, then combine the half for higher power terms.
Iterative
if n < 0:
n = -n
x = 1/x
ans = 1
cur_multi = x
while n > 0:
if n & 1 == 1:
ans *= cur_multi
cur_multi *= cur_multi
n = n >> 1
return ans
The power term n can be decomposed into binary numbers.
So we can example the binary representation of n.
We iterate through the binary representation of n and keep a cur_multi to store what the current term represent.
For example, when we are at position 1, we need to keep track of , at position 2, we need to keep
, position 4, keep
and so on.
These are the building blocks of the answer.
To get them, we simply multiple the terms from previous iteration by itself.