-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]
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.
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.
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.
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.