Pow(x, n) · DSA Prep

Multiplying x by itself n times works but wastes effort: x^8 doesn’t need 8 multiplications if you already know x^4, since x^8 = x^4 * x^4. Repeatedly squaring like this lets you skip straight to the answer using only as many multiplications as n has bits, turning a linear loop into a logarithmic one. Negative exponents are handled by flipping x to 1/x and negating n, since x^-n = (1/x)^n.

Repeated Multiplication

Time O(n)Space O(1)

Multiply x into a running result, once per unit of n. Simple, but if n is close to its constraint limit of about two billion, this loop runs about two billion times.

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

Complexity: one multiplication per unit of n → O(n) time, O(1) space.

Binary Exponentiation (Fast Power)

OptimalTime O(log n)Space O(1)

Write n in binary. Squaring x at each step doubles its exponent, so after k squarings the running base holds x^(2^k) — exactly the value needed if bit k of n is set. Walking through n’s bits from least to most significant, multiply result by the current base whenever that bit is 1, then square base and shift to the next bit.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        result = 1.0
        base = x
        while n > 0:
            if n % 2 == 1:
                result *= base
            base *= base
            n //= 2
        return result

Tracing x = 2.0, n = 10 (binary 1010): watch the examined bit decide whether its ready value is multiplied in, and see each squaring prep the next bit’s value.

bits of n = 10 — read right to left

bit 31x^(2^3)= 256

bit 20x^(2^2)= 16

bit 11x^(2^1)= 4

bit 00x^(2^0)= 2

base

= x^(2^0)

result

10 = 8 + 2 → set bits at positions 3 and 1

1 / 10

bit examinedmultiplied into resultzero bit skippedbase squaring

Start: n = 10 is positive, so the 1/x flip passes straight through. In binary this is 1010, read right to left. Squaring base once per step walks it through the values under the bits: 2, 4, 16, 256 — each one x^(2^k). Only the 1-bits (positions 1 and 3) ever multiply into the answer; result starts at 1.0, the multiplicative identity.

10 in binary is 1010, i.e. 2^3 + 2^1 = 8 + 2, so 2^10 = 2^8 * 2^2… more precisely the bits set are positions 1 and 3, giving 2^10 = base@bit1 * base@bit3 = 4 * 256 = 1024 — matching the expected output.

Correctness: n = sum of 2^k over the set bits, so x^n = product of x^(2^k) over the set bits. base holds exactly x^(2^k) when the loop examines bit k, so multiplying it into result whenever that bit is 1 accumulates precisely this product.

Complexity: n is halved every iteration → O(log n) time, O(1) space.