LeetCode 50: Pow(x, n)

Problem Restatement

We need to implement pow(x, n).

Given a floating-point number x and an integer n, return x raised to the power n.

The official problem asks us to calculate x raised to n, written as x^n. Example inputs include x = 2.00000, n = 10, which returns 1024.00000, and x = 2.00000, n = -2, which returns 0.25000.

For a negative exponent:

x ** -n = 1 / (x ** n)

For example:

2^-2 = 1 / 2^2 = 1 / 4 = 0.25

Input and Output

Function shape:

def myPow(x: float, n: int) -> float:
    ...

First Thought: Multiply Repeatedly

The simplest idea is to multiply x by itself n times.

For example:

x = 2
n = 10

We could compute:

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

This gives:

1024

Code for positive n:

result = 1.0

for _ in range(n):
    result *= x

This works for small n, but it is too slow when n is large.

LeetCode allows n to be as small as -2^31 and as large as 2^31 - 1, so an O(n) loop is not acceptable for large exponents.

Key Insight

Use binary exponentiation.

Instead of multiplying one copy of x at a time, repeatedly square the base.

For example:

x^10 = x^8 * x^2

We can get these powers by squaring:

x
x^2
x^4
x^8

The exponent 10 in binary is:

1010

That means:

10 = 8 + 2

So:

x^10 = x^8 * x^2

Binary exponentiation uses the bits of n to decide which powers of x should be multiplied into the answer.

Algorithm

First handle negative exponents.

If n < 0, change the problem from:

x^n

to:

1 / x^(-n)

Then compute the positive exponent using a loop.

Initialize:

result = 1.0
base = x
exp = abs(n)

While exp > 0:

1. If exp is odd, multiply result by base.
2. Square base.
3. Divide exp by 2 using integer division.

At the end, if the original exponent was negative, return 1 / result.

Otherwise, return result.

Walkthrough

Use:

x = 2
n = 10

Start:

result = 1
base = 2
exp = 10

Since 10 is even, do not multiply result.

Square the base:

base = 4
exp = 5

Now 5 is odd, so multiply:

result = 1 * 4 = 4

Square again:

base = 16
exp = 2

2 is even, so do not multiply.

Square again:

base = 256
exp = 1

1 is odd, so multiply:

result = 4 * 256 = 1024

Now:

exp = 0

Return:

1024

Correctness

The algorithm keeps result as the product of the powers of x selected from the binary representation of the exponent.

At each step, base represents the current power of x.

Initially, base = x, which corresponds to x^1.

After one squaring, base = x^2.

After another squaring, base = x^4.

Then x^8, x^16, and so on.

When the current exponent bit is 1, that power is part of the final answer, so the algorithm multiplies it into result.

When the bit is 0, that power is skipped.

Integer-dividing the exponent by 2 moves to the next binary bit.

Therefore, after all bits have been processed, result equals x^abs(n).

If n was negative, the mathematical definition gives:

x^n = 1 / x^(-n)

So returning the reciprocal gives the correct value.

Complexity

Implementation

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exp = abs(n)
        base = x
        result = 1.0

        while exp > 0:
            if exp % 2 == 1:
                result *= base

            base *= base
            exp //= 2

        if n < 0:
            return 1.0 / result

        return result

Code Explanation

We convert the exponent to a non-negative value:

exp = abs(n)

In Python, this is safe for very small negative integers because Python integers do not overflow.

We keep the current power in:

base = x

The result starts at 1.0 because multiplying by 1 does not change the answer:

result = 1.0

The loop processes the exponent bit by bit:

while exp > 0:

If the current exponent is odd, its lowest binary bit is 1, so we include the current base:

if exp % 2 == 1:
    result *= base

Then we square the base:

base *= base

This moves from x, to x^2, to x^4, to x^8.

Then we discard the lowest bit:

exp //= 2

Finally, if the original exponent was negative, return the reciprocal:

if n < 0:
    return 1.0 / result

Otherwise, return the computed positive power.

Testing

def almost_equal(a, b, eps=1e-9):
    return abs(a - b) < eps

def run_tests():
    s = Solution()

    assert almost_equal(s.myPow(2.0, 10), 1024.0)
    assert almost_equal(s.myPow(2.1, 3), 9.261)
    assert almost_equal(s.myPow(2.0, -2), 0.25)
    assert almost_equal(s.myPow(1.0, -2147483648), 1.0)
    assert almost_equal(s.myPow(-2.0, 3), -8.0)
    assert almost_equal(s.myPow(-2.0, 4), 16.0)
    assert almost_equal(s.myPow(5.0, 0), 1.0)

    print("all tests passed")

run_tests()