LC 50, Pow(x,n)

Calculate x^n

-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 x^{n//2} how would we get x^n. If x is even. Then x^{n} = x^{n/2} * x^{n/2}. This avoid the n/2 multiplications we used in the first step.
When n is odd, x^{n/2} * x^{n/2} will be x^{n - 1}. So we need to multiple one x back. x^n = x^{n/2} * x^{n/2} * x.

So x^n = x^{n//2} * x^{n//2} if n is even.
and x^n = x^{n/2} * x^{n/2} * 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.
x^{7} = x^{111} = x^4<em>x^2</em>x^1 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 x^1, at position 2, we need to keep x^2, position 4, keep x^4 and so on.
These are the building blocks of the answer.

To get them, we simply multiple the terms from previous iteration by itself.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax