Leetcode 50. Pow(x, n)
Asked at:
Meta
DESCRIPTION
Implement a function to compute x raised to the power n (x^n), where x is a floating-point base and n is a 32-bit signed integer (potentially negative). The solution must handle negative exponents by computing the reciprocal (1/x^|n|) and efficiently handle large magnitude exponents using exponentiation by squaring to achieve O(log |n|) time complexity. For example, myPow(2.0, -2) should return 0.25 since 2^-2 = 1/4.
Input:
x = 2.00000, n = 10
Output:
1024.00000
Explanation: 2^10 = 1024
Constraints:
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31 - 1 (32-bit signed integer)
- Result is guaranteed to fit in a double (64-bit floating point)
- n is an integer
Understanding the Problem
The core challenge is computing x^n in O(log |n|) time rather than naive O(n) multiplication. Negative exponents require computing 1/x^|n| instead of direct multiplication. The critical edge case is n = INT_MIN (-2147483648), where negating n causes integer overflow since INT_MAX is 2147483647. Exponentiation by squaring leverages the property that x^n = (x^2)^(n/2) for even n and x^n = x × x^(n-1) for odd n, reducing the problem size by half each step.
Building Intuition
The naive approach multiplies x by itself |n| times, taking O(n) time—impractical for n = 10^9. The optimized approach uses binary exponentiation: for even n, compute (x^2)^(n/2) instead of x^n, halving the problem size. For odd n, extract one x and recurse: x^n = x × x^(n-1). For example, 2^10 = (2^2)^5 = 4^5 = 4 × 4^4 = 4 × 16^2 = 4 × 256 = 1024 in just 4 steps instead of 10 multiplications.
Exponentiation by squaring is fundamental in cryptography (RSA encryption uses modular exponentiation with 2048-bit exponents), computer graphics (matrix transformations), and scientific computing (numerical simulations). Handling negative exponents correctly is essential for physics calculations (inverse square laws) and financial modeling (discount factors). The INT_MIN edge case appears in real systems where exponent ranges span the full 32-bit integer space.
Common Pitfalls
Implementation
Recursive Binary Exponentiation
Implement the recursive divide-and-conquer approach for binary exponentiation. Handle the base case n = 0 returning 1.0. For negative exponents, recursively compute myPow(1/x, -n) to convert the problem to positive exponents (use long to avoid INT_MIN overflow). For even exponents, compute half = myPow(x, n/2) and return half × half. For odd exponents, return x × myPow(x, n-1). For example, myPow(2.0, -3) becomes myPow(0.5, 3) = 0.5 × myPow(0.5, 2) = 0.5 × 0.25 = 0.125.
def myPow(x: float, n: int) -> float:if n == 0:return 1.0if n < 0:return myPow(1 / x, -n)if n % 2 == 0:half = myPow(x, n // 2)return half * halfreturn x * myPow(x, n - 1)
Iterative Binary Exponentiation
Convert the recursive approach to an iterative solution using bit manipulation to avoid stack overflow. Initialize result = 1.0 and base = x. If n < 0, set base = 1/x and convert n to positive using long to handle INT_MIN. While n > 0, check if the least significant bit is set (n & 1): if so, multiply result *= base. Then square the base (base *= base) and right-shift n (n >>= 1). For example, 2^10 (binary 1010): start with result=1, base=2, skip bit 0, square to base=4 and shift, multiply result=4 for bit 1, square to base=16 and shift, skip bit 2, multiply result=64 for bit 3.
def myPowIterative(x: float, n: int) -> float:if n == 0:return 1.0result = 1.0base = xexp = nif n < 0:base = 1 / xexp = -nwhile exp > 0:if exp & 1:result *= basebase *= baseexp >>= 1return result
Edge Case Handling and Optimization
Enhance the iterative solution with explicit edge case handling and early termination optimizations. Check n == 0 immediately and return 1.0. For x == 1.0, return 1.0 regardless of n. For x == -1.0, return 1.0 if n is even, -1.0 if odd. Handle n == INT_MIN by computing (1/x) × myPow(x, INT_MAX) to avoid overflow when negating. Add early exit in the loop when n == 0 to avoid unnecessary squaring operations. For example, myPow(-1.0, INT_MIN) returns 1.0 since INT_MIN is even, avoiding the overflow trap.
def myPowOptimized(x: float, n: int) -> float:if n == 0:return 1.0if x == 1.0:return 1.0if x == -1.0:return 1.0 if n % 2 == 0 else -1.0if n == -2147483648:return (1 / x) * myPowIterative(x, 2147483647)return myPowIterative(x, n)
What We've Learned
- Pattern: Binary exponentiation reduces `O(n)` to `O(log n)` by squaring the base and halving the exponent each iteration
- Edge Case: Convert `n` to `long` before negation to handle `INT_MIN = -2^31` without overflow
- Optimization: Use iterative bit manipulation (`n & 1`, `n >>= 1`) instead of recursion to avoid stack overflow
- Use Case: Essential for cryptographic operations (modular exponentiation), matrix exponentiation in graph algorithms, and numerical computing
Problems to Practice
medium
This problem uses binary search to find an optimal value by repeatedly halving the search space, similar to how exponentiation by squaring repeatedly squares the base and halves the exponent. Both require O(log n) time complexity and careful handling of edge cases in the binary reduction process.
This lesson provides foundational understanding of binary search and logarithmic algorithms, which directly relates to the exponentiation by squaring technique used in Pow(x,n). Understanding binary search principles helps grasp why the power function achieves O(log n) complexity.
medium
While using a different technique, this problem shares the recursive decomposition pattern where a problem of size n is broken down into smaller subproblems. Both require careful handling of base cases and edge conditions, similar to handling n=0, n=1, and negative exponents in Pow(x,n).
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early November, 2025
Meta
Mid-level
Late October, 2025
Meta
Mid-level
Late October, 2025
Meta
Mid-level
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.