Implement pow(x, n), which returns x raised to the integer power n. n can be negative and as large in magnitude as 2³¹.
Before you code
Multiplying n times is far too slow for n near 2 billion. Halve the exponent instead: x¹⁰ is (x⁵)², and x⁵ is x × (x²)².
Hints
- Base case: n == 0 returns 1.
- Compute the half power once, store it, and square it. Calling the function twice on n // 2 makes the tree branch and loses the speedup.
- For negative n, compute the power for −n and take the reciprocal. Careful: in 32-bit languages, −(−2³¹) overflows; convert to a 64-bit integer first.
- The iterative version reads the bits of n: square x for each bit, and multiply it into the result when the bit is 1.
Production & complexity notes
When solving Pow(x, n) on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Base cases and recursion trees to reinforce the underlying pattern.
What it practices
The difference between a chain and a branching recursion tree, from Base cases and recursion trees.