Domain 2MediumCORE

Pow(x, n)

We need to compute $x^n$ where x is a floating-point base and n is an integer exponent. The result must be accurate within standard float precision constraints ($-10^4 le x^n le 10^4$).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Binary Search

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 xnx^n where x is a floating-point base and n is an integer exponent. The result must be accurate within standard float precision constraints (−104≤xn≤104-10^4 \le x^n \le 10^4).

Key inputs: Float x, Integer n. Implicit constraints & edge cases to consider immediately:

  • Negative Exponent: If n<0n < 0, we are calculating the reciprocal of a positive power (1x−n\frac{1}{x^{-n}}). We must handle this before applying binary exponentiation logic.
  • Minimum Integer Overflow (in other languages): In fixed-width integer environments, negating Integer.MIN_VALUE overflows. While Python handles arbitrary precision integers automatically, we should conceptually acknowledge the need to handle −231-2^{31} carefully in a robust implementation.
  • Zero Base: If x=0x = 0, 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 O(n)O(n). If n=−231n = -2^{31} (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 (xa)b=xab(x^a)^b = x^{ab}. Specifically:
    • If nn is even (n=2kn=2k), then xn=(x2)kx^n = (x^2)^k.
    • If nn is odd, we peel off one factor of x and 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 O(n)O(n) to O(log⁡n)O(\log n).

Approach

I will implement an iterative Binary Exponentiation algorithm for efficiency and stack safety compared to recursion.

Steps:

  1. Handle negative exponents by inverting the base (x←1/xx \leftarrow 1/x) and making n positive. 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.
  2. Initialize a result variable (res) at 1.0 (multiplicative identity).
  3. Iterate while n > 0:
    • If the least significant bit of n is odd (n&1n \& 1), multiply res by current base x.
    • Square the base (x *= x).
    • Right shift (divide) n by 2.
  4. Return res.

Complexity Analysis

  • Time: O(log⁡∣n∣)O(\log |n|). We divide the exponent by 2 in every iteration, so we perform roughly log⁡2(n)\log_2(n) iterations. Each step is constant time arithmetic operations on floats/ints.
  • Space: O(1)O(1). 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 x before loop.
    • Note: If n=−231n = -2^{31}, Python handles the negation correctly without overflow logic required in C++.
  • Zero Base (x=0x=0): The code returns 0 for any valid non-negative power implicitly (if input is valid per constraints). If n was negative and x was 0 initially, it would raise a ZeroDivisionError on the reciprocal step. Given problem constraints guarantee bounded output range, this implies x≠0x \neq 0 when n<0n < 0.
  • 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).