LeetCode 50 - Pow(x, n)

The problem asks us to implement exponentiation manually, specifically computing: where x is a floating point number and n is an integer exponent. The input consists of two values: - x, the base - n, the exponent The output should be the result of raising x to the power n.

leetcodemediummathrecursion

LeetCode Problem 50

Difficulty: 🟡 Medium
Topics: Math, Recursion

Solution

Problem Understanding

The problem asks us to implement exponentiation manually, specifically computing:

$$x^n$$

where x is a floating point number and n is an integer exponent.

The input consists of two values:

  • x, the base
  • n, the exponent

The output should be the result of raising x to the power n.

A few examples clarify the behavior:

  • 2^10 = 1024
  • 2.1^3 = 9.261
  • 2^-2 = 1 / (2^2) = 1/4 = 0.25

The constraints are important because they immediately rule out naive solutions for large exponents.

The exponent range is:

$$-2^{31} \le n \le 2^{31}-1$$

This means n can be extremely large, around 2 billion in magnitude. A solution that multiplies x by itself |n| times would be far too slow in the worst case.

The problem also includes negative exponents. Mathematically:

$$x^{-n} = \frac{1}{x^n}$$

So if the exponent is negative, we must invert the base and work with the positive exponent.

Another subtle issue is integer overflow in some languages. In particular, -(-2^31) overflows a 32 bit signed integer in languages like Java or C++. Python handles large integers automatically, but Go still requires careful handling when converting negative exponents.

The problem guarantees:

  • Either x != 0
  • Or n > 0

This prevents undefined cases like 0^-1.

Important edge cases include:

  • n = 0, since any nonzero number to the zero power equals 1
  • Negative exponents
  • Very large exponents
  • Negative bases
  • Fractional bases
  • Minimum integer exponent, -2^31

These cases can easily break naive implementations if not handled carefully.

Approaches

Brute Force Approach

The simplest idea is to multiply x repeatedly.

If n is positive:

$$x^n = x \times x \times x \times \dots$$

performed n times.

If n is negative, we compute:

$$x^{-n}$$

and then take the reciprocal.

This approach is straightforward and correct because exponentiation is literally repeated multiplication.

However, the time complexity is linear in the exponent magnitude:

$$O(|n|)$$

With n potentially around 2 billion, this is completely impractical.

Optimal Approach, Binary Exponentiation

The key observation is that exponentiation has a recursive structure.

Consider:

$$x^{10}$$

Instead of multiplying x ten times, we can write:

$$x^{10} = (x^5)^2$$

and:

$$x^5 = x \times (x^2)^2$$

Each step cuts the exponent roughly in half.

This technique is called binary exponentiation, exponentiation by squaring, or fast power.

The central idea is:

  • If n is even:

$$x^n = (x^{n/2})^2$$

  • If n is odd:

$$x^n = x \times x^{n-1}$$

By repeatedly halving the exponent, the algorithm runs in logarithmic time instead of linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O( n )
Optimal O(log n )

Algorithm Walkthrough

We will use the iterative version of binary exponentiation because it avoids recursion overhead and uses constant extra space.

  1. Handle negative exponents.

If n is negative, we use the mathematical identity:

$$x^{-n} = \frac{1}{x^n}$$

So we replace:

  • x with 1/x
  • n with -n

After this transformation, we only need to solve the positive exponent case. 2. Initialize the result.

Start with:

result = 1

This works because multiplying by 1 does not change the value. 3. Process the exponent bit by bit.

The exponent is treated like a binary number.

For example:

$$13_{10} = 1101_2$$

which means:

$$x^{13} = x^8 \times x^4 \times x^1$$

Each binary digit tells us whether a power contributes to the final answer. 4. If the current exponent bit is odd, multiply the result.

When n % 2 == 1, the current power of x should be included in the answer.

So we do:

result *= x
  1. Square the base.

After processing the current bit, we move to the next power:

x *= x

This generates:

$$x, x^2, x^4, x^8, x^{16}, \dots$$ 6. Halve the exponent.

Move to the next binary digit:

n //= 2
  1. Repeat until the exponent becomes zero.

Once all binary digits are processed, result contains the final answer.

Why it works

Binary exponentiation works because every integer can be represented as a sum of powers of two.

For example:

$$13 = 8 + 4 + 1$$

Therefore:

$$x^{13} = x^8 \times x^4 \times x^1$$

The algorithm systematically generates these powers by repeated squaring and multiplies only the ones corresponding to set bits in the exponent. Since the exponent is halved each iteration, the number of operations is logarithmic.

Python Solution

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # Handle negative exponents
        if n < 0:
            x = 1 / x
            n = -n

        result = 1.0

        while n > 0:
            # If current bit is set
            if n % 2 == 1:
                result *= x

            # Square the base
            x *= x

            # Move to next bit
            n //= 2

        return result

The implementation begins by checking whether the exponent is negative. If it is, the base is inverted and the exponent is converted to positive. This transforms the problem into a standard positive exponent calculation.

The variable result starts at 1.0, which acts as the multiplicative identity.

The while loop processes the exponent one binary digit at a time. Whenever the current exponent is odd, the current power of x contributes to the final answer, so it is multiplied into result.

The base is squared each iteration because each step moves to the next power of two:

$$x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8$$

Finally, the exponent is halved using integer division. This discards the binary digit that has already been processed.

When the exponent reaches zero, all bits have been handled and the result is complete.

Go Solution

func myPow(x float64, n int) float64 {
    exponent := int64(n)

    // Handle negative exponents
    if exponent < 0 {
        x = 1 / x
        exponent = -exponent
    }

    result := 1.0

    for exponent > 0 {
        // If current bit is set
        if exponent%2 == 1 {
            result *= x
        }

        // Square the base
        x *= x

        // Move to next bit
        exponent /= 2
    }

    return result
}

The Go solution follows the same algorithmic structure as the Python implementation.

One important Go specific detail is converting n to int64. This prevents overflow when handling the minimum integer value:

$$-2^{31}$$

Negating this value directly in a 32 bit signed integer type would overflow. Using int64 safely accommodates the conversion.

Unlike Python, Go uses explicit floating point types such as float64, so all arithmetic is performed with that type.

Worked Examples

Example 1

Input:

x = 2.0
n = 10

Binary representation of 10:

1010
Iteration n n Odd? result x
Start 10 No 1 2
1 10 No 1 4
2 5 Yes 4 16
3 2 No 4 256
4 1 Yes 1024 65536

Final answer:

1024

Example 2

Input:

x = 2.1
n = 3

Binary representation of 3:

11
Iteration n n Odd? result x
Start 3 Yes 2.1 4.41
1 1 Yes 9.261 19.4481

Final answer:

9.261

Example 3

Input:

x = 2.0
n = -2

First transform:

x = 1 / 2 = 0.5
n = 2
Iteration n n Odd? result x
Start 2 No 1 0.5
1 1 Yes 0.25 0.25

Final answer:

0.25

Complexity Analysis

Measure Complexity Explanation
Time O(log n
Space O(1) Only a few variables are used

The exponent decreases by a factor of two during every loop iteration. Therefore, the number of iterations equals the number of binary digits in n, which is logarithmic.

The iterative implementation uses constant extra memory because it stores only a small fixed number of variables regardless of input size.

Test Cases

solution = Solution()

# Provided examples
assert solution.myPow(2.0, 10) == 1024.0  # basic positive exponent
assert abs(solution.myPow(2.1, 3) - 9.261) < 1e-9  # decimal base
assert solution.myPow(2.0, -2) == 0.25  # negative exponent

# Zero exponent
assert solution.myPow(5.0, 0) == 1.0  # any number to power 0

# Base equals 1
assert solution.myPow(1.0, 1000000) == 1.0  # always 1

# Negative base with odd exponent
assert solution.myPow(-2.0, 3) == -8.0  # negative result

# Negative base with even exponent
assert solution.myPow(-2.0, 4) == 16.0  # positive result

# Fractional base
assert solution.myPow(0.5, 3) == 0.125  # repeated division effect

# Large exponent
assert solution.myPow(2.0, 30) == 1073741824.0  # stress logarithmic performance

# Minimum exponent edge case
result = solution.myPow(2.0, -2147483648)
assert result > 0  # verifies no overflow/crash

# Very small base
assert abs(solution.myPow(0.0001, 2) - 1e-8) < 1e-15  # precision handling

# Zero base with positive exponent
assert solution.myPow(0.0, 5) == 0.0  # valid zero power case

Test Case Summary

Test Why
2.0, 10 Standard exponentiation
2.1, 3 Floating point multiplication
2.0, -2 Negative exponent handling
5.0, 0 Zero exponent identity
1.0, 1000000 Stable repeated multiplication
-2.0, 3 Negative base with odd exponent
-2.0, 4 Negative base with even exponent
0.5, 3 Fractional base
2.0, 30 Large exponent performance
2.0, -2147483648 Minimum integer exponent
0.0001, 2 Precision behavior
0.0, 5 Zero base edge case

Edge Cases

Negative Exponents

Negative exponents are one of the most common sources of mistakes. A naive implementation might attempt repeated multiplication directly with a negative loop bound, which does not make mathematical sense.

The correct transformation is:

$$x^{-n} = \frac{1}{x^n}$$

The implementation handles this immediately by inverting the base and converting the exponent to positive before entering the main loop.

Minimum Integer Exponent

The value:

$$-2^{31}$$

is problematic in fixed width integer systems because its positive counterpart cannot be represented in the same signed range.

In Go, negating this value directly using a 32 bit integer could overflow. The solution avoids this by converting the exponent to int64 before negation.

Python integers automatically expand, so the Python implementation does not suffer from this issue.

Zero Exponent

Mathematically:

$$x^0 = 1$$

for all nonzero x.

Some implementations accidentally return 0 or skip handling this case. In this algorithm, result starts at 1, and the loop never executes when n == 0, so the correct value is naturally returned.

Negative Bases

Negative bases require careful handling because the sign depends on whether the exponent is even or odd.

Examples:

$$(-2)^3 = -8$$

$$(-2)^4 = 16$$

Binary exponentiation preserves this behavior automatically because it uses ordinary multiplication rules throughout the computation.