[Medium] 50. Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).
Examples
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25
Constraints
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31-1
- n is an integer.
- Either x is not zero or n > 0.
- -10^4 <= x^n <= 10^4
Thinking Process
There are two main approaches to implement exponentiation efficiently:
- Recursive Approach: Use divide-and-conquer with recursion
- Iterative Approach: Use bit manipulation and iterative computation
Both approaches achieve O(log n) time complexity by reducing the problem size by half in each step.
Common Approaches
Typical techniques for this pattern:
| Approach | Time | Space | Notes |
|---|---|---|---|
| XOR tricks (this problem) | O(n) | O(1) | Single number, swap without temp |
| Bit masks | O(2^n) | O(n) | Subset enumeration |
| Brian Kernighan | O(log n) | O(1) | Count set bits |
| Shift operations | O(n) | O(1) | Power of two, divide by 2 |
Solution
java
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1, cur = x;
for (long i = N; i > 0; i /= 2) {
if ((i & 1) == 1) ans *= cur;
cur *= cur;
}
return ans;
}
}
Solution Explanation
Approach: XOR tricks (this problem)
Key idea: There are two main approaches to implement exponentiation efficiently:
How the code works:
- Recursive Approach: Use divide-and-conquer with recursion
- Iterative Approach: Use bit manipulation and iterative computation
Walkthrough — input x = 2.00000, n = 10, expected output 1024.00000:
- Initialize variables from the problem setup.
- Apply the main loop / recursion until the condition is met.
- Confirm the result matches the expected output.
Step-by-Step Example (Solution 2)
For x = 2, n = 10:
- Initial: rtn = 1, x = 2, n = 10 (binary: 1010)
- n = 10 (even): x = 4, n = 5
- n = 5 (odd): rtn = 4, x = 16, n = 2
- n = 2 (even): x = 256, n = 1
- n = 1 (odd): rtn = 1024, x = 65536, n = 0
- n = 0: return 1024
Common Mistakes
- Integer overflow when n = -2^31 (can’t negate directly)
- Not handling negative exponents properly
- Naive O(n) approach instead of O(log n)
- Precision issues with floating point arithmetic
- n = 0: return 1.0
- n = 1: return x
- n = -1: return 1/x
- x = 0: return 0 (if n > 0)
- x = 1: return 1 for any n
Related Problems
References
- LC 50: Pow(x, n) on LeetCode
- LeetCode Discuss — LC 50: Pow(x, n)
- LeetCode Editorial (may require premium)
Key Takeaways
- Divide and Conquer: x^n = (x^(n/2))^2 for even n, x^n = (x^(n/2))^2 * x for odd n
- Negative Exponents: x^(-n) = 1/x^n
- Integer Overflow: Use
long longto handle n = -2^31 case - Bit Manipulation: Iterative approach uses binary representation of n