50. Pow(x, n)
Model: qwen3.5:9b
Topics: Math,Binary Search
FAANG asked: 1
Acceptance rate: 31.0%
Problem Breakdown
We need to compute where x is a floating-point base and n is an integer exponent. The result must be accurate within standard float precision constraints ().
Key inputs: Float x, Integer n.
Implicit constraints & edge cases to consider immediately:
- Negative Exponent: If , we are calculating the reciprocal of a positive power (). We must handle this before applying binary exponentiation logic.
- Minimum Integer Overflow (in other languages): In fixed-width integer environments, negating
Integer.MIN_VALUEoverflows. While Python handles arbitrary precision integers automatically, we should conceptually acknowledge the need to handle carefully in a robust implementation. - Zero Base: If , any positive power is 0. A negative or zero exponent with base 0 results in division by zero (undefined). Given the output constraints, we assume valid inputs where this doesn’t produce infinity unless specified otherwise.
Intuition
A naive solution would multiply x into itself n times using a loop.
- Brute Force: Time Complexity . If (approx 2 billion), we perform billions of multiplications, which will definitely cause a Time Limit Exceeded (TLE).
- Optimization Insight: We can use the property that . Specifically:
- If is even (), then .
- If is odd, we peel off one factor of
xand solve for the remaining exponent.
- This reduces the problem size by half at each step (squaring the base). We only need to multiply into our result when the current bit of the exponent is 1.
- Result: Time Complexity drops from to .
Approach
I will implement an iterative Binary Exponentiation algorithm for efficiency and stack safety compared to recursion.
Steps:
- Handle negative exponents by inverting the base () and making
npositive. This simplifies the loop logic. Note: In Python, we don’t strictly need to worry about integer overflow on negation like C++, but logically it’s cleaner. - Initialize a result variable (
res) at 1.0 (multiplicative identity). - Iterate while
n > 0:- If the least significant bit of
nis odd (), multiplyresby current basex. - Square the base (
x *= x). - Right shift (divide)
nby 2.
- If the least significant bit of
- Return
res.
Complexity Analysis
- Time: . We divide the exponent by 2 in every iteration, so we perform roughly iterations. Each step is constant time arithmetic operations on floats/ints.
- Space: . We use a fixed number of variables regardless of input size (iterative approach).
Solution
class Solution:
def myPow(self, x: float, n: int) -> float:
# Handle negative exponent by inverting base and making n positive.
# Python handles large integer negation automatically without overflow issues
# that fixed-width languages (C++/Java) face at Integer.MIN_VALUE.
if n < 0:
x = 1 / x
n = -n
res = 1.0
while n > 0:
# If current bit of exponent is set, multiply result by base
if n & 1 == 1:
res *= x
# Square the base for next iteration (x^(2k))
x *= x
# Move to next bit in exponent
n >>= 1
return res
Edge Cases Handled
- Negative Exponent: Converted to positive by taking reciprocal of
xbefore loop.- Note: If , Python handles the negation correctly without overflow logic required in C++.
- Zero Base (): The code returns 0 for any valid non-negative power implicitly (if input is valid per constraints). If
nwas negative andxwas 0 initially, it would raise a ZeroDivisionError on the reciprocal step. Given problem constraints guarantee bounded output range, this implies when . - Floating Point Precision: Standard float multiplication is used; Python’s double precision handles the required accuracy for LeetCode test cases without custom epsilon logic (which would complicate code unnecessarily).