Pow(x, n)
mediumTime: O(log n)Space: O(log n)
Signals to notice
compute x^n efficientlyhalve the exponenthandle negative n
Brute force first
Multiply x by itself n times — O(n). Linear in the exponent.
The key insight
Binary exponentiation: x^n = (x²)^(n/2) if even, x × x^(n-1) if odd. Halves n each step. O(log n).
What must stay true
Squaring the base and halving the exponent reduces any exponent to 0 in O(log n) steps. Negative n: compute x^|n| then take 1/result.
Easy way to go wrong
Integer overflow for n = -2^31 — |n| overflows int32. Handle this edge case with long/BigInt.