LeetCode 50 · Math & Geometry · concepts: math-and-geometry, bit-manipulation

Problem

Compute x raised to the power n (n may be negative).

Approach — fast (binary) exponentiation (optimal)

Multiplying x by itself n times is O(n). Exponentiation by squaring is O(log n): xⁿ = (x²)^(n/2) for even n, and x · x^(n−1) for odd n — halving the exponent each step. Reading the exponent’s binary digits, you square the base each step and multiply it into the result whenever the current bit is set.

def myPow(x, n):
    if n < 0:                          # x^-n = (1/x)^n
        x, n = 1 / x, -n
    result = 1
    while n:
        if n & 1:                      # current lowest bit set -> include this power of x
            result *= x
        x *= x                         # square the base for the next bit
        n >>= 1                        # move to the next bit
    return result

Time O(log n), space O(1).

Why squaring halves the work

Each squaring doubles the exponent that x represents (x, x², x⁴, x⁸, …). The binary representation of n says which of those powers to multiply together — so you need only log₂ n multiplications instead of n. The n & 1 / n >>= 1 walk over n’s bits is why this ties directly to bit manipulation.

Key insight

Exponentiation (or any associative “repeat k times”) → binary exponentiation, O(log n) via squaring. The same doubling idea powers matrix exponentiation (O(log n) Fibonacci) and modular exponentiation in cryptography.

↑ Back to NeetCode 150 — Solved