Pow(x, n)

Problem

Implement pow(x, n), which raises the floating-point number x to the integer power n (that is, compute x**n). The exponent n can be negative, zero, or positive.

Do not use a built-in power function. Compute the result yourself, in far fewer than n multiplications.

Examples

• x = 2.0, n = 10 → 1024.0 — 2 multiplied by itself ten times.
• x = 2.1, n = 3 → 9.261000000000001 — ordinary floating-point cube (tiny rounding is expected).
• x = 2.0, n = -2 → 0.25 — a negative exponent means 1 / x**|n|, so 1 / 4.

Constraints

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31 - 1 (n fits in a 32-bit signed integer).
• x is nonzero when n is negative; the result stays within double-precision range.
• Because |n| can be ~2 billion, an O(n) loop is far too slow — you need O(log n).

Think about it first

TL;DR

Binary (fast) exponentiation — square the base while halving the exponent — O(log n) time, O(1) space iterative (or O(log n) stack recursive).

Approach 1 — Brute force (multiply n times)

Multiply x into an accumulator |n| times, then reciprocate if n was negative.

def myPow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    for _ in range(n):
        result *= x
    return result

Complexity: O(n) time, O(1) space.

Correct, but with n as large as 2^31 - 1 this is about two billion multiplications — it times out. The constraints are chosen precisely to forbid the linear loop.

Approach 2 — Binary exponentiation, recursive

Exponentiation splits in half: x**n = (x**(n//2))**2 for even n, with one extra factor of x for odd n. Each recursive call halves the exponent, so the recursion depth, and the number of multiplications, is O(log n).

This is fast exponentiation (exponentiation by squaring): a divide-and-conquer that turns n multiplications into log n squarings.

def myPow(x: float, n: int) -> float:
    def power(base: float, exp: int) -> float:
        if exp == 0:
            return 1.0
        half = power(base, exp // 2)
        if exp % 2 == 0:
            return half * half
        return half * half * base

    if n < 0:
        return power(1 / x, -n)
    return power(x, n)

Walkthrough with x = 2.0, n = 10:

• power(2, 10) → needs power(2, 5), then squares it.
• power(2, 5) → needs power(2, 2), squares, times 2 (odd).
• power(2, 2) → needs power(2, 1), squares.
• power(2, 1) → needs power(2, 0) = 1, squares = 1, times 2 (odd) = 2.
• Back up: power(2, 2) = 2*2 = 4; power(2, 5) = 4*4*2 = 32; power(2, 10) = 32*32 = 1024.

The calls form a single chain: descend by halving the exponent, then multiply the squared results back up.

flowchart TD
    A["power(2, 10)"] --> B["power(2, 5)"]
    B --> C["power(2, 2)"]
    C --> D["power(2, 1)"]
    D --> E["power(2, 0)"]
    E -. "returns 1" .-> D
    D -. "1·1·2 = 2" .-> C
    C -. "2·2 = 4" .-> B
    B -. "4·4·2 = 32" .-> A
    A --> R["result = 32·32 = 1024"]

Only 4 levels of recursion instead of 10 multiplications, and the gap widens as n grows.

Complexity: O(log n) time, O(log n) space for the call stack.

Approach 3 — Binary exponentiation, iterative

The same idea without recursion. Read the exponent bit by bit: keep squaring x (covering x**1, x**2, x**4, x**8, …), and whenever the current low bit of n is 1, fold that power into the result. This is x**n = product of x**(2^k) over the set bits k of n.

def myPow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n > 0:
        if n & 1:            # current low bit set
            result *= x
        x *= x               # square the base for the next bit
        n >>= 1
    return result

Walkthrough with x = 2.0, n = 10 (1010 in binary):

The set bits of 10 are at positions 1 and 3, so the answer is 2**2 * 2**8 = 4 * 256 = 1024.

Complexity: O(log n) time, O(1) space — the preferred production form.

Common pitfalls

• Forgetting n == 0 → must return 1.0 (any base, including 0.0**0 by convention here).
• Negative exponent handling: convert to 1/x with a positive exponent. In fixed-width languages, -(-2^31) overflows; promote to a wider type first. Python’s arbitrary-precision ints sidestep this, but it’s the classic interview gotcha.
• Recomputing power(base, exp // 2) twice instead of storing it once — that silently turns O(log n) back into O(n).
• Expecting exact floats: 2.1**3 is 9.261000000000001; small rounding is normal, not a bug.

Pattern takeaway

Whenever an operation is associative and you must apply it n times — powers, matrix powers, modular exponentiation — halve the exponent and square the operand: O(n) collapses to O(log n). Reading the exponent’s binary digits (“apply the accumulated square exactly on set bits”) is the reusable iterative skeleton.