Pow(x, n)

PracticeNeetCode ↗LeetCode ↗

Implement pow(x, n), computing x raised to the power n, where n can be negative.

Example

Key Pointers

• Multiplying x by itself n times is O(n); halving the exponent each step (fast exponentiation) gets it to O(log n).
• x^n = (x^(n/2))^2 when n is even, and x^n = x^(n-1) · x when n is odd — recursing on that split is what halves the work each call.
• A negative n is just 1 / x^(-n) — handle the sign once up front and work with a non-negative exponent from then on.

Step-by-Step Analysis

1. If n is negative, compute the answer as 1 / helper(x, -n) instead.
2. Base case: if the exponent is 0, return 1.
3. Recursively compute half = helper(x, exp // 2).
4. If the exponent is even, the result is half * half; if odd, it's half * half * x.

Complexity

Time: O(log n) — Space: O(log n) recursion stack

Code

def myPow(x: float, n: int) -> float:
    def helper(base: float, exp: int) -> float:
        if exp == 0:
            return 1.0
        half = helper(base, exp // 2)
        if exp % 2 == 0:
            return half * half
        return half * half * base

    if n < 0:
        return 1 / helper(x, -n)
    return helper(x, n)

Code Explanation

How the solution above works, piece by piece.

1. helper(base, exp) computes base^exp for exp ≥ 0 using x^n = (x^(n/2))².
2. Compute the half power once, half = helper(base, exp // 2), and square it.
3. If exp is odd, integer division dropped one factor, so multiply by base once more.
4. A negative exponent means the reciprocal: 1 / helper(x, -n).
5. O(log n) multiplications and recursion depth.

Visual Walkthrough

Running it on x = 2.0, n = 10:

Video Explanation

NeetCode — X to the power of N, LeetCode 50