Pow(x, n)
Problem
Given a floating-point number x and an integer n, return x raised to the power n (i.e., x^n).
- −100.0 < x < 100.0
- −2³¹ ≤ n ≤ 2³¹ - 1
Example
x = 2.0, n = 101024.0A naive approach would multiply 2.0 by itself 10 times, resulting in 1024.0. However, this requires 10 multiplications. The recursive divide and conquer approach reduces the number of multiplications by repeatedly squaring the base and halving the exponent. For example, 2^10 = (2^5)^2. The recursion continues until the exponent reaches zero (base case), returning 1. The critical moment is when the exponent is odd, requiring an extra multiplication by the base to account for the leftover factor.
Approach
Straightforward Solution
A straightforward solution multiplies x by itself n times, resulting in O(n) time complexity, which is inefficient for large n.
Core Observation
Exponentiation can be expressed recursively as x^n = (x^2)^(n//2) when n is even, and x * (x^2)^(n//2) when n is odd. This reduces the problem size by half at each step, enabling logarithmic time complexity.
Path to Optimal
Recognizing that repeated multiplication can be optimized by squaring the base and halving the exponent leads to a divide and conquer approach. This reduces the number of multiplications from linear to logarithmic in n. Handling negative exponents requires computing the reciprocal of the positive exponent result.
Optimal Approach
Implement a recursive helper function that returns 1 if n is zero, returns 0 if x is zero, and otherwise recursively computes helper(x*x, n//2). If n is odd, multiply the result by x. The main function calls this helper with the absolute value of n and returns the result or its reciprocal depending on the sign of n.
Time
O(log n)
Each recursive call halves the exponent n, leading to a recursion depth of log n. Each call performs a constant number of multiplications.
Space
O(log n)
The recursion stack depth is proportional to log n due to halving the exponent at each step. No additional significant auxiliary space is used.
Pattern Spotlight
Divide and Conquer (Exponentiation by Squaring)
To compute powers efficiently, recursively reduce the exponent by half each step by squaring the base, and multiply by the base once more if the exponent is odd; this transforms O(n) multiplications into O(log n).
Solution
| 1 | class Solution:
|
| 2 | def myPow(self, x: float, n: int) -> float:
|
| 3 | def helper(x, n):
|
| 4 | if x == 0: return 0
|
| 5 | if n == 0: return 1
|
| 6 |
|
| 7 | res = helper(x * x, n // 2)
|
| 8 | return x * res if n % 2 else res
|
| 9 |
|
| 10 | res = helper(x, abs(n))
|
| 11 | return res if n >= 0 else 1 / res |
Step-by-Step Solution
Handle Negative and Zero Exponents with Recursive Helper
| 4 | if x == 0: return 0
|
| 5 | if n == 0: return 1
|
| 7 | res = helper(x * x, n // 2)
|
Objective
To correctly compute power for positive exponents and handle zero and zero-base edge cases.
Key Insight
The recursive helper function uses divide and conquer by squaring the base and halving the exponent, which reduces the problem size exponentially. It returns 1 when the exponent is zero, as any number to the zero power is 1, and returns 0 immediately if the base is zero, as zero to any positive power is zero. This base case handling prevents unnecessary recursion and ensures correctness.
Interview Quick-Check
Core Logic
The helper function recursively computes power by squaring the base and halving the exponent, returning 1 for exponent zero and 0 for base zero.
State & Boundaries
Base cases prevent infinite recursion and handle mathematical edge cases: x == 0 returns 0, n == 0 returns 1.
Common Pitfalls & Bugs
Failing to handle zero base or zero exponent correctly can lead to incorrect results or infinite recursion.
Combine Recursive Results and Handle Odd Exponents
| 8 | return x * res if n % 2 else res
|
Objective
To combine the recursive results by multiplying the squared base power and adjusting for odd exponents.
Key Insight
After recursively computing helper(x*x, n//2), the algorithm checks if n is odd. If so, it multiplies the result by x to account for the extra factor lost during integer division of n by 2. This step ensures the correctness of the exponentiation for odd powers while maintaining logarithmic complexity.
Interview Quick-Check
Core Logic
Multiplying by x when n is odd corrects for the truncated exponent in the recursive call, preserving the exact power.
Common Pitfalls & Bugs
Omitting the multiplication for odd exponents leads to incorrect results, especially for odd powers.
Adjust Final Result for Negative Exponents
| 10 | res = helper(x, abs(n))
|
| 11 | return res if n >= 0 else 1 / res |
Objective
To compute the final power value by handling negative exponents via reciprocal.
Key Insight
Since the helper function only computes powers for non-negative exponents, the main function calls it with the absolute value of n. If n is negative, the final result is the reciprocal of the helper's output, implementing the mathematical rule x^-n = 1 / x^n. This separation simplifies the recursive logic and ensures correctness for all integer exponents.
Interview Quick-Check
Core Logic
Using the reciprocal for negative exponents correctly implements the mathematical definition of negative powers.
Common Pitfalls & Bugs
Failing to handle negative exponents leads to incorrect results or infinite recursion.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if n == 0: return 1Return 1 if the exponent n is zero.
Any number raised to the zero power is 1, making this the essential base case for terminating recursion.
return x * res if n % 2 else resMultiply by x if n is odd, otherwise return the recursive result directly.
Multiplying by x when n is odd accounts for the lost factor due to integer division, ensuring the correctness of the exponentiation.
res = helper(x * x, n // 2)Recursively compute helper(x squared, n halved).
This line implements the divide and conquer step by reducing the problem size exponentially, enabling O(log n) time complexity.
return res if n >= 0 else 1 / resReturn the result or its reciprocal depending on the sign of n.
This line implements the mathematical rule for negative exponents by returning the reciprocal of the positive power, ensuring correctness for all integer exponents.
if x == 0: return 0Return 0 immediately if the base x is zero.
Zero raised to any positive power is zero, so returning 0 here prevents unnecessary recursion and correctly handles this edge case.
res = helper(x, abs(n))Call the helper function with the absolute value of n.
This isolates the recursive logic to positive exponents, simplifying the implementation and avoiding negative exponent complications within recursion.
Test Your Understanding
Why does the algorithm multiply by x only when the exponent n is odd?
Because when n is odd, dividing it by 2 truncates the exponent, losing one factor of x. Multiplying by x once more accounts for this leftover factor, ensuring the correctness of the exponentiation.
Related Problems
Math pattern
Don't just read it. Drill it.
Reconstruct Pow(x, n) from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Pow(x, n) drill