LeetCode 50 · Math & Geometry

Pow(x, n), explained with a picture

Folding paper to multiply fast.

MediumMath & Geometry
▶ Watch it step by step

The problem

Compute x raised to the power n (n may be negative) faster than multiplying x by itself n times.

Input:  x = 2, n = 10
Output: 1024

Picture it

Picture folding paper: each fold doubles the thickness. x¹⁰ = (x⁵)², and x⁵ = x · (x²)². So we look at n in binary: square x at each step, and multiply it into the answer whenever the current bit of n is 1. A negative power means 1 ÷ (positive power).

How to recognise it

  • You compute a power of a number where the exponent can be huge (up to about 2 billion).
  • Multiplying n times is too slow, but the result is a plain product of identical factors.
  • The exponent can be split in halves: x^n is related to (x^(n/2))².
  • Looking at the binary digits of n gives a short list of squarings.
  • Negative exponents appear, and mean "one divided by the positive power".

Start with brute force

Multiply x by itself n times.

def pow_brute(x, n):
    result = 1.0
    for _ in range(abs(n)):
        result *= x
    return result if n >= 0 else 1 / result

Time is O(|n|) and space O(1). With |n| up to 2^31 (about 2.1 billion) that is billions of multiplications, which would take minutes in Python and is too slow for a typical time limit.

From brute force to the idea

  1. Square instead of repeat. x^10 = (x^5)² and x^5 = x · (x²)². One squaring replaces many multiplications.
  2. Read n in binary. For example 10 is 1010. Then x^10 = x^8 · x^2, which is the product of the powers x^(2^k) at the positions where the bit is 1.
  3. Walk through the bits. The loop keeps x equal to x, x², x⁴, x⁸ and so on (x *= x). At each step, if the lowest bit of n is 1 (n & 1), multiply the result by the current x. Then drop that bit with n >>= 1.
  4. Handle negative n first. x, n = 1 / x, -n turns x^(−n) into (1/x)^n, so the loop only sees non-negative exponents.
  5. n = 0 skips the loop and returns 1.

This is the key idea: n has only about 31 binary digits, so about 31 squarings plus up to 31 multiplications give the answer.

The key idea

Fast exponentiation by squaring: O(log n) multiplications.

Python solution

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1
    while n:
        if n & 1:
            result *= x        # this power of two is in n
        x *= x                 # square: x, x², x⁴, x⁸ …
        n >>= 1
    return result

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(\n\): one multiplication per unit of the exponentO(1)
Squaring by bits (shown code)O(log \n\): one loop step per bit, at most 62 multiplications for 32 bitsO(1)

For n = 2^31 − 1 the shown code does 62 multiplications, while the brute force needs more than 2 billion.

Edge cases

  • n = 0: returns 1, even for x = 0 (my_pow(0, 0) is 1).
  • Negative exponent (my_pow(2, -2)): returns 0.25.
  • Negative base (my_pow(-2, 3) is −8, my_pow(-2, 4) is 16): the sign follows the parity of n.
  • x = 0 with a negative exponent: 1 / x raises ZeroDivisionError. The problem says that x = 0 only comes with positive n.
  • Smallest exponent (n = −2^31): Python integers have no limit, so -n is fine. In languages with 32-bit integers, -n overflows and needs a wider type.
  • Overflow and underflow: my_pow(2.0, 2**31 - 1) returns inf, and my_pow(2.0, -1075) returns 0.0. These are float limits, not bugs.
  • Result type: my_pow(2, 10) returns the int 1024, while a negative exponent returns a float.
  • Rounding: my_pow(2.1, 3) is 9.261000000000001, a small floating-point error that LeetCode accepts.

Common mistakes

  • Not handling negative n. The loop never ends, because -2 >> 1 stays at −1 forever.
  • Forgetting to square x each step, so only the first power is used: my_pow(2, 10) becomes 4.
  • Squaring before the bit test, which uses x² where x is needed: my_pow(2, 3) becomes 64 (see the quiz).
Your turn: powers modulo m

Compute x^n modulo m (n ≥ 0, all integers), for numbers whose true power is far too large to hold. For x = 2, n = 10, m = 1000 the answer is 24. Describe your approach, then write it if you like.

Compare with our answer

Same loop, but reduce every product modulo m so the numbers stay small. This is valid because (a · b) mod m = ((a mod m) · (b mod m)) mod m.

def pow_mod(x, n, m):
    result = 1 % m                  # 1 % 1 is 0, so m = 1 works
    x %= m
    while n:
        if n & 1:
            result = result * x % m
        x = x * x % m
        n >>= 1
    return result

pow_mod(2, 10, 1000) is 24, pow_mod(3, 200, 13) is 9, pow_mod(5, 0, 1) is 0, and it agrees with Python's built-in pow(x, n, m) on thousands of random cases. Time O(log n), space O(1).

A strong answer mentions: reducing after every multiplication, starting from 1 % m, and why modulo does not break the squaring idea.

Check what stuck

1. You must find the last digit of 7 raised to the power 10^9. Which approach fits best?

2. Why is the shown code O(log n) instead of O(n)?

3. A learner swaps the lines inside the loop, so x *= x comes before the if n & 1: test. What does my_pow(2, 3) return?

Score 60% or more and the lesson is marked complete.