LeetCode 50: Pow(x, n) Solution in Python Explained

Problem Statement

LeetCode 50, Pow(x, n), is a medium-level problem where you’re given a floating-point number x and an integer n. Your task is to compute x raised to the power n (i.e., (x^n)) and return it as a float. You must implement this efficiently, avoiding naive repeated multiplication, and handle edge cases like negative exponents and overflow within the constraints.

Constraints

-100.0 < x < 100.0: Base x is within this range.
-2^31 <= n <= 2^31 - 1: Exponent n is a 32-bit signed integer.
-10^4 <= x^n <= 10^4: Result must fit within this range.

Example

Input: x = 2.00000, n = 10
Output: 1024.00000
Explanation: 2^10 = 1024.

Input: x = 2.10000, n = 3
Output: 9.26100
Explanation: 2.1^3 = 9.261.

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 0.25.

Understanding the Problem

How do you solve LeetCode 50: Pow(x, n) in Python? For x = 2.0 and n = 10, compute (2^{10} = 1024.0) efficiently. Naive multiplication (multiplying x by itself n times) is O(n) and impractical for large n. We’ll explore two approaches: a Fast Power with Recursion Solution (optimal and primary) and an Alternative with Iterative Approach (also efficient but different). The fast power method uses divide-and-conquer to achieve O(log n) time by leveraging the binary representation of n.

Solution 1: Fast Power with Recursion Approach (Primary)

Explanation

Use the fast power algorithm (exponentiation by squaring): compute (x^n) by breaking (n) into powers of 2. If (n) is even, (x^n = (x^{n/2})^2); if odd, (x^n = x * (x^{(n-1)/2})^2). Handle negative (n) by computing (1/x^{|n|}). Recursively halve the exponent, reducing the problem size.

Here’s a flow for (2^{10}):

2^10 = (2^5)^2
2^5 = 2 * (2^4)
2^4 = (2^2)^2
2^2 = (2^1)^2
2^1 = 2 * 2^0
Result: 1024

Base Cases.

\(n = 0\), return 1; \(x = 0\), return 0.

Handle Negative (n).

Convert to positive, adjust \(x\).

Recursive Step.

Half \(n\), square result, multiply by \(x\) if odd.

Return Result.

Step-by-Step Example

Example 1: x = 2.0, n = 10

We need 1024.0.

Goal: Compute \(2^{10}\).
Result for Reference: 1024.0.
Start: x = 2.0, n = 10.
Step 1: \(n = 10\), even.

\(2^{10} = (2^5)^2\), recurse with \(n = 5\).

Step 2: \(n = 5\), odd.

\(2^5 = 2 * (2^4)\), recurse with \(n = 4\).

Step 3: \(n = 4\), even.

\(2^4 = (2^2)^2\), recurse with \(n = 2\).

Step 4: \(n = 2\), even.

\(2^2 = (2^1)^2\), recurse with \(n = 1\).

Step 5: \(n = 1\), odd.

\(2^1 = 2 * (2^0)\), recurse with \(n = 0\).

Step 6: \(n = 0\), return 1.0.
Step 7: Backtrack.

\(2^1 = 2 * 1 = 2\).
\(2^2 = 2^2 = 4\).
\(2^4 = 4^2 = 16\).
\(2^5 = 2 * 16 = 32\).
\(2^{10} = 32^2 = 1024\).

Finish: Return 1024.0.

Example 2: x = 2.0, n = -2

We need 0.25.

Start: \(n = -2\), \(x = 1/2 = 0.5\).
Step 1: \(n = 2\), even.

\(0.5^2 = (0.5^1)^2\), recurse with \(n = 1\).

Step 2: \(n = 1\), odd.

\(0.5^1 = 0.5 * (0.5^0)\), recurse with \(n = 0\).

Step 3: \(n = 0\), return 1.0.
Step 4: \(0.5^1 = 0.5 * 1 = 0.5\), \(0.5^2 = 0.5^2 = 0.25\).
Finish: Return 0.25.

How the Code Works (Recursive Fast Power)

Here’s the Python code with line-by-line explanation:

def myPow(x: float, n: int) -> float:
    # Line 1: Base cases
    if n == 0:
        return 1.0
    if x == 0:
        return 0.0

    # Line 2: Handle negative n
    if n < 0:
        x = 1 / x
        n = -n

    # Line 3: Recursive fast power
    def fastPow(x: float, n: int) -> float:
        # Line 4: Base case
        if n == 0:
            return 1.0
        # Line 5: Half the exponent
        half = fastPow(x, n // 2)
        # Line 6: Even or odd n
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

    # Line 7: Call helper and return
    return fastPow(x, n)

Alternative: Iterative Fast Power Approach

Explanation

Use an iterative approach to compute (x^n) by processing (n)’s binary representation. For each bit in (n), square the current result, and if the bit is 1, multiply by (x). This avoids recursion while maintaining O(log n) time.

Handle Negative (n).
Iterate Bits.

Square result, multiply by \(x\) for 1 bits.

3. Return Result.

Step-by-Step Example (Alternative)

For (x = 2.0, n = 10) (binary 1010):

Start: \(n = 10\), \(x = 2.0\), result = 1.0.
Step 1: \(n = 1010\).

Bit 0: 0, result = 1, x = 2^2 = 4.
Bit 1: 1, result = 1 * 4 = 4, x = 4^2 = 16.
Bit 2: 0, result = 4, x = 16^2 = 256.
Bit 3: 1, result = 4 * 256 = 1024, x = 256^2.

Finish: Return 1024.0.

How the Code Works (Iterative)

def myPowIterative(x: float, n: int) -> float:
    # Line 1: Base cases
    if n == 0:
        return 1.0
    if x == 0:
        return 0.0

    # Line 2: Handle negative n
    if n < 0:
        x = 1 / x
        n = -n

    # Line 3: Initialize result
    result = 1.0
    current = x

    # Line 4: Process n’s binary bits
    while n > 0:
        # Line 5: If bit is 1, multiply result
        if n % 2 == 1:
            result *= current
        # Line 6: Square current
        current *= current
        # Line 7: Shift n right
        n //= 2

    # Line 8: Return result
    return result

Complexity

Recursive Fast Power:

Time: O(log n) – Halve exponent each step.
Space: O(log n) – Recursion stack depth.

Iterative Fast Power:

Time: O(log n) – Process each bit of n.
Space: O(1) – Only variables.

Efficiency Notes

Both are O(log n) time, far better than O(n) naive multiplication. Iterative uses O(1) space, slightly more efficient than Recursive’s O(log n) stack, but both are suitable for LeetCode 50.

Key Insights

Tips to master LeetCode 50:

Divide and Conquer: Halve exponent for speed.
Binary Insight: \(n\)’s bits guide multiplication.
Edge Cases: Handle 0, negative \(n\), and overflow.

Additional Example

For (x = 3.0, n = 4):

Goal: 81.0.
Recursive: \(3^4 = (3^2)^2 = 9^2 = 81\).
Result: 81.0.

Edge Cases

\(n = 0\): Return 1.0.
\(x = 0, n < 0\): Undefined, but per constraints, return 0.0.
Negative \(n\): \(2^{-3} = 1/8\).

Final Thoughts

The Fast Power with Recursion solution is a sleek choice for LeetCode 50 in Python—efficient, elegant, and logarithmic. For a related challenge, try LeetCode 49: Group Anagrams to switch gears with strings! Ready to power up? Solve LeetCode 50 on LeetCode now and test it with (2.0^{10}) or (1.5^5) to master fast exponentiation. Dive in and raise the bar!