Pow(x, n) - Video Solutions

Problem Overview: Implement pow(x, n), which returns x raised to the power n. The tricky part is handling large exponents and negative powers efficiently without multiplying x exactly n times.

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

The simplest strategy repeatedly multiplies x by itself n times. Start with a result value of 1, iterate from 1 to n, and update result *= x. If n is negative, compute the power for |n| and return 1/result. This approach is straightforward but inefficient for large values of n because it performs n multiplications. It demonstrates the core idea of exponentiation but quickly becomes too slow when n is large.

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

This optimized approach reduces the number of multiplications using the mathematical identity: x^n = (x^2)^(n/2). Instead of multiplying x repeatedly, square the base while halving the exponent. If the current exponent is odd, multiply the result by the current base before squaring. Continue shifting the exponent using integer division until it becomes zero. This technique processes the exponent bit-by-bit, similar to binary exponentiation, which cuts the number of operations from n to log₂(n). It works well for very large powers and avoids recursion overhead. The algorithm relies purely on arithmetic operations from Math concepts.

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

The recursive version follows the same exponentiation-by-squaring principle but expresses it with recursion. Compute half = pow(x, n/2). If n is even, return half * half. If n is odd, multiply once more with x. For negative exponents, convert the problem using x^-n = 1 / x^n. Each recursive call halves the exponent, producing a recursion depth of log₂(n). This approach is clean and easy to reason about because it directly mirrors the mathematical recurrence, making it a common demonstration of recursion and divide-and-conquer strategies.

Recommended for interviews: Interviewers usually expect exponentiation by squaring with O(log n) complexity. The iterative version is slightly preferred because it avoids recursion stack overhead and shows awareness of performance tradeoffs. Explaining the naive O(n) method first demonstrates understanding of the problem, while transitioning to the logarithmic solution shows algorithmic optimization skills.