LeetCode 50 · Medium · Math & Geometry

Pow(x, n)

Compute x raised to the integer power n, which may be negative, without a built-in power function.

O(log n)time
O(log n)recursion depth
square and halvebinary exponentiation

x: −10 to 10, up to 2 decimals · n: whole number −99 to 99 · x = 0 needs n > 0

Call chain each call squares x and halves n · the dark tag is the value it returns

|n| in binary call d reads bit d: a 1 multiplies in one more x2^d

public double myPow(double x, int n) { double res = helper(x, Math.abs((long) n)); return n >= 0 ? res : 1 / res;}private double helper(double x, long n) { if (x == 0) { return 0; } if (n == 0) { return 1; } double res = helper(x * x, n / 2); return n % 2 == 1 ? x * res : res;}
depth
—
x
—
n
—
res
—

Why it works

  1. Brute force multiplies n times: O(n) multiplications. Fine for 10, hopeless for n near 2³¹.
  2. Halve the exponent: xⁿ = (x²)n/2 when n is even, and x · (x²)(n−1)/2 when n is odd. Each call squares the base and halves the exponent, so the chain is only about log₂ n calls deep.
  3. It is the binary of n: call d holds x2^d and looks at bit d of n. A 1 bit multiplies that power into the result on the way back up; a 0 bit passes the result through. 13 = 1101₂ gives x⁸ · x⁴ · x¹.
  4. Pitfall: negative n. Compute with the absolute value, then take the reciprocal. Math.abs(Integer.MIN_VALUE) is still negative, because 2³¹ does not fit in an int: widen n to a long first, as in Math.abs((long) n).
  5. Cost: O(log n) multiplications and O(log n) stack frames. A loop over the bits of n does the same work in O(1) space.
  6. Related: the same square-and-multiply idea gives modular exponentiation (RSA) and fast matrix powers (Fibonacci in O(log n)).