Pow(x, n) - Video Solutions

Problem Overview: The task is to implement pow(x, n), which returns x raised to the power n. The challenge comes from handling very large exponents efficiently, including negative values of n, without relying on built‑in power functions.

Approach 1: Naive Multiplication (O(n) time, O(1) space)

The most straightforward solution multiplies x by itself n times. You iterate from 1 to n, repeatedly updating the result with result *= x. For negative powers, compute 1 / x^|n|. This approach works but becomes extremely slow for large exponents because it performs one multiplication per step. It demonstrates the basic idea but fails typical interview constraints where n may be up to billions.

Approach 2: Iterative Exponentiation by Squaring (O(log n) time, O(1) space)

This optimized approach repeatedly squares the base while halving the exponent. The key observation is that x^n can be written as (x^2)^(n/2) when n is even, and x * x^(n-1) when n is odd. Using this property, you iterate while n > 0, multiply the result when the current bit of the exponent is odd, then square the base and divide the exponent by two. Because the exponent shrinks by half each step, the algorithm runs in logarithmic time. This method relies on simple arithmetic operations and fits naturally within topics like math and efficient power computation.

Approach 3: Recursive Divide and Conquer (O(log n) time, O(log n) space)

The recursive version applies the same exponentiation by squaring logic but expresses it using recursion. If n is even, compute pow(x, n/2) once and square the result. If n is odd, multiply x with the result of pow(x, n-1). The recursion depth is proportional to log n because the exponent is halved each time. The algorithm is clean and closely reflects the mathematical recurrence, making it a common teaching example in recursion and divide and conquer strategies. The tradeoff is additional call stack space compared to the iterative solution.

Recommended for interviews: Interviewers typically expect exponentiation by squaring. Start by explaining the naive multiplication approach to show baseline reasoning, then move to the logarithmic solution. The iterative implementation is usually preferred because it avoids recursion overhead while maintaining O(log n) time and constant space.