Pow(x, n)
mediumTime: O(log n)Space: O(log n)
Recognize the pattern
compute x^n efficientlyhalve the exponenthandle negative n
Brute force idea
Multiply x by itself n times — O(n). Linear in the exponent.
Better approach
Binary exponentiation: x^n = (x²)^(n/2) if even, x × x^(n-1) if odd. Halves n each step. O(log n).
Key invariant
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.
Watch out for
Integer overflow for n = -2^31 — |n| overflows int32. Handle this edge case with long/BigInt.