Pow(x, n): Fast Exponentiation by Squaring

Given a floating-point number x and an integer n, compute x raised to the power n. That is, implement pow(x, n).

This is LeetCode 50: Pow(x, n). A few examples:

• x = 2.0, n = 10 returns 1024.0
• x = 2.1, n = 3 returns 9.261
• x = 2.0, n = -2 returns 0.25

A brute force loop multiplying x by itself n times works, but it is O(n). For n = 2**31 - 1, that is over two billion multiplications. The real solution uses exponentiation by squaring to get the answer in O(log n) multiplications.

The approach

The key insight is that you can halve the exponent at every step. Instead of computing x * x * x * ... * x a total of n times, you use this identity:

• If n is even: x^n = (x^(n/2))^2
• If n is odd: x^n = (x^(n/2))^2 * x
• Base case: x^0 = 1

For x^10, instead of 10 multiplications, you compute:

1. x^10 = (x^5) * (x^5)
2. x^5 = (x^2) * (x^2) * x
3. x^2 = (x^1) * (x^1)
4. x^1 = (x^0) * (x^0) * x
5. x^0 = 1

That is only 4 levels of recursion, each doing one or two multiplications. The exponent halves at every level, so the total depth is O(log n).

Handling negative exponents

When n is negative, x^n = 1 / x^(-n). You invert x (replace x with 1/x) and negate n, then use the same squaring logic. One subtle edge case: if n is -2**31, negating it overflows a 32-bit integer. In Python this is not an issue because Python integers have arbitrary precision, but it is worth noting for other languages.

Python solution

def myPow(x, n):
    if n < 0:
        x = 1 / x
        n = -n

    def helper(x, n):
        if n == 0:
            return 1.0
        half = helper(x, n // 2)
        if n % 2 == 0:
            return half * half
        return half * half * x

    return helper(x, n)

Walkthrough

Let's trace through pow(2.0, 10) step by step. The recursion goes down to the base case first, then combines results on the way back up.

At every level, you compute half = pow(x, n // 2) once, then reuse that value by squaring it. This is what turns O(n) multiplications into O(log n). You never recompute the same subproblem.

Iterative version

The recursive solution uses O(log n) stack space. You can eliminate that with an iterative approach that processes the bits of n from least significant to most significant:

def myPow(x, n):
    if n < 0:
        x = 1 / x
        n = -n

    result = 1.0
    current = x

    while n > 0:
        if n % 2 == 1:
            result *= current
        current *= current
        n //= 2

    return result

This version runs in O(log n) time and O(1) space. At each step, current holds x^(2^k) for increasing k. When the k-th bit of n is set, you multiply current into the result.

Complexity analysis

Both squaring approaches do the same number of multiplications. The difference is that the iterative version avoids recursion overhead and uses constant space.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• n = 0: return 1.0. Any number (including 0) raised to the power 0 is 1 by convention, but 0^0 is debatable in math. LeetCode expects 1.
• n is negative: invert x and negate n. Do not forget this or you will get wrong answers for negative exponents.
• x = 0: 0^n for positive n is 0. For negative n, this would be division by zero (1/0), but LeetCode does not test this case.
• x = 1: 1^n is always 1 regardless of n. No special handling needed, but it is a good sanity check.
• Large n: n can be up to 2^31 - 1 or as low as -2^31. The O(log n) approach handles this in about 31 steps.
• Negative n = -2^31: negating this overflows a 32-bit integer. In Python this is fine. In C++ or Java, convert to a long first.

The building blocks

This problem is built on two reusable patterns:

Exponentiation by squaring. The core technique: reduce the exponent by half at each step and square the intermediate result. This applies anywhere you need to compute x^n efficiently, including modular exponentiation in cryptography and matrix exponentiation for computing Fibonacci numbers in O(log n).

Divide-and-conquer on the exponent. Instead of processing the exponent linearly, you split it in half and combine the results. This is the same divide-and-conquer principle behind merge sort and binary search, applied to a mathematical operation instead of a data structure.

These two building blocks are tightly coupled in this problem. Recognizing that "halving the exponent" is a divide-and-conquer strategy, and that "squaring the result" is how you combine the halves, gives you the full algorithm.

From understanding to recall

You have walked through the recursive decomposition, the iterative bit-processing version, and the edge cases. The logic makes sense now. But reading a solution and producing one under pressure are different skills.

The next time you see a problem that involves repeated multiplication or large exponents, you want "exponentiation by squaring" to surface immediately. That only happens if you have practiced the pattern enough times that the decomposition is automatic: check parity, recurse on half, square, maybe multiply by x.

Spaced repetition locks this in. You solve the problem from scratch today, again in two days, then four days, then a week. Each time, you rebuild the recursive structure and the iterative version from memory. After a few rounds, the pattern is yours.

Related posts

• Climbing Stairs - Another problem where breaking a computation into smaller subproblems (here, Fibonacci-style recurrence) is the key to efficiency
• Divide Two Integers - Uses the same "double and subtract" strategy with bit shifts to avoid brute-force repeated subtraction