4.28.6 — Pow(x, n)

LeetCode 50 · Medium

The problem

Compute x raised to the power n, where n may be negative.

pow(2.0, 10)    →  1024.0
pow(2.0, -2)    →  0.25
pow(2.1, 3)     →  9.261

n ranges over the full 32-bit signed integer range.

The pattern

Multiplying x by itself n times is O(n) — two billion multiplications at the limit.

Fast exponentiation does it in O(\log n), using one identity:

x^n = \begin{cases} (x^{n/2})^2 & n \text{ even} \\ x \cdot x^{n-1} & n \text{ odd} \end{cases}

Each even step halves the exponent, so the number of steps is \log_2 n. For n = 1,000,000,000 that is about 30 multiplications instead of a billion.

The iterative form is easier to get right than the recursion, and it comes from reading the exponent in binary:

x^{13} = x^{8+4+1} = x^8 \cdot x^4 \cdot x^1

13 is 1101 in binary. So: square x repeatedly to get x^1, x^2, x^4, x^8, and multiply in the ones whose bit is set.

This is the same idea as binary representation itself, which is why it belongs next to the bit-manipulation chapter.

The negative-exponent trap

x^{-n} = 1 / x^n, so the obvious move is to negate n and invert at the end.

But negating the most negative 32-bit integer overflows. The range is -2^{31} to 2^{31}-1, so -(-2^{31}) does not fit.

In Python integers are unbounded and this cannot happen. In Java, C++ or C it can, and the standard fix is to widen n to a 64-bit type before negating.

Mention it. It is exactly the kind of detail that separates someone who has thought about the range from someone who has not, and this problem's constraints are worded to invite the question.

The solution

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n

        result = 1.0
        while n:
            if n & 1:                 # this bit of the exponent is set
                result *= x
            x *= x                    # x, x², x⁴, x⁸, …
            n >>= 1                   # move to the next bit

        return result

TypeScript

function myPow(x: number, n: number): number {
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  while (n > 0) {
    if (n % 2 === 1) result *= x;
    x *= x;
    n = Math.floor(n / 2);
  }

  return result;
}

n & 1 tests the lowest bit — whether n is odd. n >>= 1 divides by two, discarding that bit. Together they walk the exponent's binary representation from the least significant end.

x *= x on every iteration, whether or not the bit was set, because the next bit represents twice the exponent.

result starts at 1, which is what makes n = 0 return 1 with no special case.

In JavaScript use Math.floor(n / 2) rather than n >>= 1 — the bitwise operators coerce to 32-bit signed integers, which would break for large n.

Trace

x = 2, n = 13 (binary 1101).

n	binary	bit set?	result	x
13	1101	yes	2	4
6	110	no	2	16
3	11	yes	32	256
1	1	yes	8192	—

2^{13} = 8192 ✓. The multiplications used were x^1 \cdot x^4 \cdot x^8, matching 1101.

The recursive form

def myPow(self, x, n):
    if n < 0:
        return 1 / self.myPow(x, -n)
    if n == 0:
        return 1.0
    half = self.myPow(x, n // 2)
    return half * half if n % 2 == 0 else half * half * x

half must be computed once and reused. Writing myPow(x, n//2) * myPow(x, n//2) makes two recursive calls instead of one, and the whole thing collapses back to O(n). That is the classic mistake here, and it is the same "compute once, use twice" discipline as memoisation.

O(\log n) stack depth, which is fine at 32 levels.

Floating point honesty

Repeated multiplication accumulates rounding error. pow(2.0, 10) is exact because powers of two are exact in binary, but pow(2.1, 3) will be very slightly off from 9.261 — LeetCode accepts a small tolerance for this reason.

For integer bases with a modulus, the identical algorithm with % m after each multiplication is modular exponentiation, and it is the operation RSA is built on. Chapter 8 covers that, and mentioning it here shows the algorithm is not a puzzle.

Complexity

O(\log n) time, O(1) space iteratively.

Where this goes next

• Modular exponentiation — the same loop with % m, and the core of RSA and Diffie-Hellman.
• Matrix exponentiation — replace the multiplication with matrix multiplication and you can compute the n-th Fibonacci number in O(\log n). A neat connection back to 4.23.1.
• Super Pow (LeetCode 372) — the exponent itself is an array of digits.
• Sqrt(x) — binary search on the answer instead. 4.11.

What the interviewer will push on

"Why is it O(\log n)?" The exponent halves every iteration.

"What goes wrong with negative n?" Negating the most negative integer overflows in fixed-width languages.

"Why does the recursive version need half in a variable?" Two recursive calls would make it O(n).

"What about floating-point error?" It accumulates; exact answers need integer or rational arithmetic.

"What if you needed the result modulo something?" Apply % m after each multiplication — that is modular exponentiation, and it is what public-key cryptography runs on.

One thing to volunteer: explain the algorithm in terms of the exponent's binary digits. "13 is 1101, so I need x^8 \cdot x^4 \cdot x^1." It makes the loop obviously correct instead of a trick.

Next: 4.28.7 Multiply Strings — long multiplication, and the index formula that makes it work.