Pattern Recognition Drill
Medium Math & Geometry
The Problem
Implement pow(x, n) — compute x raised to the power n.
What approach would you use?
Think about it before scrolling down.
x^n = (x^(n/2))². If n is odd, multiply by x. O(log n).
Iterative: square x and halve n, accumulating when n is odd. Same O(log n).
Common Trap
Handle n < 0 by computing 1/x^(-n). Watch for integer overflow when negating n.