Pow(x, n) — The Paper Fold

Boss 6: The Paper Fold

This boss looks like a joke. Compute x ** n? Python has an operator for it. But the operator has to be implemented by someone, and the technique inside it — fast exponentiation — is one of the most reused ideas in all of computing. It powers RSA handshakes, O(log n) Fibonacci, hashing, and half of number theory. The final dungeon would be incomplete without it.

And it's a reunion boss. The halving instinct comes straight from Dungeon 4, and the implementation is pure Dungeon 17 bit-walking.

The story

A paper craftsman gets a commission from a mathematician with too much money: "Start with a strip x millimeters thick. I want the thickness after it doubles n times. And n is around two billion."

The craftsman starts the honest way — glue a copy of the stack onto itself, one layer operation at a time, updating a running thickness. Then he does the arithmetic on his own lifespan and puts the brush down.

While thinking, he absent-mindedly folds the strip in half. And stares.

One fold doubled the entire stack. Not one layer added — everything he had, doubled in a single motion. Fold again: four layers. Ten folds: 1024 layers, not ten. The number of layers isn't the number of operations. It's two raised to the number of operations.

That's the whole weapon. Don't multiply a million times to get x to the millionth power. Fold: square what you have, and the exponent doubles for free.

The problem, dressed up properly

Implement pow(x, n), which calculates x raised to the power n. Here n is a 32-bit signed integer and can be negative.

LeetCode 50, "Pow(x, n)". Medium-rated, deceptively short, and the canonical home of binary exponentiation.

The naive attempt

Glue one layer at a time:

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    for _ in range(n):
        result *= x     # one glue stroke
    return result

Correct. Now the lifespan arithmetic. The exponent can be as large as 2^31 - 1, which is 2,147,483,647. If the craftsman glues one layer per second, that's about 2.1 billion seconds — roughly 68 years of non-stop gluing. He'd finish the order sometime in his next life.

A computer is faster, but not saved: an interpreted Python loop grinds through maybe ten million iterations a second, so this runs for minutes and blows straight past any time limit. Meanwhile log2(2^31) is 31. Thirty-one folds cover what two billion glue strokes cover. That gap — decades versus a blink — is the entire lesson of logarithmic time.

The weapon: fold, don't glue

Squaring is the fold. If you already hold x^k, one multiplication gives you x^k * x^k = x^(2k). The exponent doubles per operation, so you reach n in about log2(n) steps.

Reading it top-down: to get x^n, first get x^(n // 2), square it, and if n was odd, multiply one extra loose x — the layer that didn't fit in the fold.

Halving the problem until it's trivial — that's the same instinct as Dungeon 4's binary search. Koko halved a speed range, the Warehouse Deadline halved an answer space, and here we halve the exponent. Different objects, same knife.

The iterative version is even better, and it's a straight Dungeon 17 flashback. Write n in binary: the binary expansion is the recipe. 13 = 1101 in binary, so x^13 = x^8 * x^4 * x^1 — one factor per set bit. Walk n's bits with n & 1 and n >> 1, squaring the base every step so it's always x, x^2, x^4, x^8... and multiply the base into the result exactly when the current bit is 1.

def my_pow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1.0 / x, -n   # x^-n == (1/x)^n
    result = 1.0
    base = x                 # x^1, x^2, x^4, x^8, ... the folded strip
    while n:
        if n & 1:            # this power of two is in the recipe
            result *= base
        base *= base         # fold: exponent of base doubles
        n >>= 1              # next bit
    return result

One caution on that first line: in Python, negating n is always safe because integers are arbitrary-width. In Java or C++, n = -2^31 is a trap — its positive twin doesn't fit in 32 bits, so negate after widening to a 64-bit type, or the negation silently overflows back to itself.

Watching it work

Compute x^13. In binary, 13 is 1101, read right to left as bits 1, 0, 1, 1.

n (binary)  bit   result                base (after squaring)
1101         1    1 * x    = x^1        x^2
110          0    x^1 (unchanged)       x^4
11           1    x^1 * x^4 = x^5       x^8
1            1    x^5 * x^8 = x^13      x^16 (never used)

Four loop turns. Three result multiplications, four squarings — about seven multiplications total instead of twelve, and the gap explodes with size: x^(2^31) is 31 loop turns instead of two billion.

Negative exponent? x^-13 flips the base to 1/x, negates n to 13, and the exact same walk runs. The fold doesn't care which direction the thickness grows.

Gotchas

1. Forgetting the odd leftover x. x^13 is not (x^6)^2. That's x^12 — the loose layer that didn't fit in the fold got dropped. Every time you halve an odd exponent, one bare x must be set aside and multiplied back in. The iterative version encodes this as the n & 1 check; skip it and every odd bit of n silently vanishes.

2. Negating n in a fixed-width language. n = -2^31 fits in a 32-bit int, but 2^31 does not. Writing n = -n in Java or C++ overflows and hands you a negative "positive" exponent that never reaches zero. Widen to a 64-bit long first, then negate. Python users get this one free, which is exactly why interviewers love asking about it.

3. Trusting floats at huge exponents. Each multiplication rounds a little, and x^(2^31) for x near 1 accumulates real drift — plus anything with |x| meaningfully above 1 overflows to infinity long before the loop ends. LeetCode's judge tolerates the drift, but this is why serious applications (crypto, combinatorics) run the same algorithm on integers under a modulus, where every step is exact.

4. Recursing without halving. return x * my_pow(x, n - 1) is the glue-one-layer loop wearing a recursion costume: O(n) time and O(n) stack frames, which is a stack overflow around n in the tens of thousands, never mind two billion. A subtler cousin: recursing with my_pow(x, n // 2) * my_pow(x, n // 2) calls the half-problem twice and lands right back at O(n) multiplications. Compute the half once, store it, square the stored value.

Complexity

The loop runs once per bit of n, and n has at most 32 bits.

Time: O(log n). Space: O(1) for the iterative version (the recursive one pays O(log n) stack).

Boss down

The craftsman ships the order the same afternoon: thirty-one folds, a note about which folds got an extra loose sheet, and an invoice the mathematician can't argue with. Two billion glue strokes, refused on principle.

That's six of eight in the final dungeon. Boss 7 is Multiply Strings — The Abacus Clerk: a clerk asked to multiply numbers so large no register, no long, no 64-bit anything can hold them. The only way through is the way schoolchildren and abacus beads have always done it — digit by digit, cell by cell, carrying as you go. Bring paper.