# LC 50, Pow(x,n)

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.

Posted on Categories Leetcode