Pow(x, n)

Pow(x, n) asks you to compute x raised to the power n. The naive loop multiplies x by itself n times — but a classic trick computes the same answer in O(log n) by squaring the base and halving the exponent.

The slow way first

The obvious idea: start at 1.0 and multiply by x exactly n times. That works, but it is O(n) — for n = 1,000,000,000 that is a billion multiplications. Far too slow.

The question to ask: can I reuse work instead of redoing it? Computing x^2 gives me x^4 for one more multiply, then x^8, then x^16... Each squaring doubles the exponent I have covered, so I reach x^n in about log n steps.

The idea: square the base, halve the exponent

Write n in binary. Every power of x we need is a power-of-two power (x^1, x^2, x^4, x^8, ...), and x^n is the product of the ones whose bit is set. So walk the bits of n from the bottom: keep a running x that you square each step, and whenever the current bit is 1 (that is, n is odd), fold the running x into result. Then halve n and repeat until it reaches 0.

Negative exponents are handled up front: x^-n = (1/x)^n, so we replace x with 1/x and flip n positive, then run the same loop.

Walk through it

Step through the animation with x = 2.0, n = 10. The three cells are x, n, and result. Watch x square (2 → 4 → 16 → 256), n halve (10 → 5 → 2 → 1 → 0), and result pick up a factor only on the odd steps (n = 5 and n = 1). After just 4 iterations result is 1024.0.

Pseudocode

result = 1.0
if n is negative:
    x = 1 / x          # x^-n = (1/x)^n
    n = -n
while n > 0:
    if n is odd:
        result = result * x   # fold in this power-of-two power
    x = x * x          # square the base
    n = n // 2         # drop the lowest bit
return result

The Python solution

def my_pow(x, n):
    result = 1.0
    if n < 0:
        x = 1 / x
        n = -n
    while n > 0:
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2
    return result

• result starts at 1.0, the identity for multiplication.
• The if n < 0 block turns a negative exponent into a positive one by inverting x.
• n % 2 == 1 tests whether the current lowest bit is set — i.e. whether n is odd.
• Line 8 is the only place we touch result: we fold in the running x exactly when the bit is 1.
• x *= x squares the base, and n //= 2 drops the bit we just handled, shrinking the problem each pass.

Complexity

The exponent is halved every pass, so the loop runs about log2(n) times — for a billion, roughly 30 steps instead of a billion. The iterative version uses O(1) extra space (a recursive version would use O(log n) stack frames).

When this pattern shows up

Practice