Pow(x, n) (LeetCode 50)

The problem

Implement pow(x, n): raise a floating-point number x to an integer power n, where n can be negative or zero. You may not call the built-in power operator.

Input:  x = 2.0, n = 10
Output: 1024.0

2 multiplied by itself 10 times is 1024. For n = -2 the answer would be 1 / 2² = 0.25.

How to think about it

Start with brute force. Multiply x into a result n times. That is O(n) multiplications. With n up to about 2³¹ (two billion), it is far too slow, and it is exactly what the interviewer wants you to improve.

The key insight: squaring doubles the exponent. From x you get x² in one multiplication, then x⁴, x⁸, x¹⁶, and so on. After k squarings you have x^(2^k). Any exponent is a sum of powers of two, which is just its binary form: 10 = 1010 in binary = 8 + 2, so x¹⁰ = x⁸ · x². So walk the bits of n from the lowest: keep squaring x, and whenever the current bit is 1, multiply the current x into the result. There are only about log₂ n bits, so only O(log n) multiplications.

Negative exponents are a one-line fix. x^(-n) = (1/x)^n. Flip x to 1/x and n to -n at the start, and the same loop works.

Which pattern is this? Binary exponentiation (also called fast power or square-and-multiply), from the math family. The tell is “implement pow” or “compute a huge power”, often with “mod M” added. The same idea powers modular exponentiation and matrix exponentiation for Fibonacci-style recurrences.

Approach

1. If n is negative, replace x with 1 / x and n with -n.
2. Start res = 1.
3. While n is not 0: if the lowest bit of n is 1, multiply res by x.
4. Square x and shift n right by one bit.
5. Return res.

Solution

def my_pow(x, n):
    if n < 0:
        x = 1 / x; n = -n          # x^-n = (1/x)^n
    res = 1
    while n:
        if n & 1:
            res *= x               # this bit is set: include current power of x
        x *= x; n >>= 1            # x -> x^2, move to the next bit
    return res
# my_pow(2.0, 10) -> 1024.0 ;  my_pow(2.0, -2) -> 0.25

Dry run

On x = 2.0, n = 10 (binary 1010). The x column is its value when the bit is checked:

The two set bits pick up x² = 4 and x⁸ = 256, and 4 × 256 = 1024.0. Four loop steps instead of ten multiplications.

Complexity

• Time: O(log n). Each step halves n, so the loop runs once per bit of n.
• Space: O(1). Only x, n and res. A recursive version (pow(x, n/2) squared) is also O(log n) time but uses O(log n) stack.

Edge cases and pitfalls

• n = 0 returns 1 for any x: the loop never runs.
• Negative n must flip x to 1/x. Forgetting this either loops forever or returns the wrong value, depending on the language.
• n = -2³¹ in Java/C++. Negating it overflows a 32-bit int. Copy n into a 64-bit long before negating. Python has no such limit.
• x = 0 with negative n divides by zero; the problem’s constraints rule it out, but mention it.
• Squaring x before checking the bit shifts every power by one place and gives the wrong answer. Check the bit, then square.

Related problems

• Number of 1 Bits (LeetCode 191): the same n & 1, n >>= 1 walk over the bits of a number.
• Sum of Two Integers (LeetCode 371): another arithmetic operation rebuilt from bit operations.
• Multiply Strings (LeetCode 43): implement a basic arithmetic operation yourself, digit by digit.