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.