50. Pow(x, n)

Problem¶

Implement myPow(x, n) to compute \(x^n\) for a floating-point x and integer n.

• Handle negative powers by returning the reciprocal.
• The solution should be efficient enough for very large n.

Example:

x = 2.0, n = -2 -> 0.25

Key trick¶

Use binary exponentiation:

• If n is even, compute \((x^2)^{n/2}\)
• If n is odd, compute x * x^(n-1)
• If n < 0, convert to positive exponent and invert the result

This reduces time from \(O(|n|)\) to \(O(\log |n|)\).

Trap¶

Common mistakes:

• Looping |n| times, which times out for large n
• Forgetting to handle negative n
• Missing the special case n == 0
• Recursing without reducing the exponent correctly
• Not being careful with floating-point precision

Why is it interesting?¶

It tests whether you know how to turn a naive repeated multiplication into a logarithmic-time algorithm using exponent properties. It is a very common interview check for recursion, iterative optimization, and edge-case handling.

Python solution¶

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # Fast exponentiation in O(log |n|).
        if n == 0:
            return 1.0

        if n < 0:
            x = 1 / x
            n = -n

        ans = 1.0
        base = x

        while n > 0:
            # If the current bit is set, multiply by the current base.
            if n & 1:
                ans *= base
            # Square the base and shift to the next bit.
            base *= base
            n >>= 1

        return ans

Comment on my solution¶

Your solution is correct in logic for positive powers, but it is too slow for large n because it multiplies x exactly |n| times.

The main issue is this part:

for _ in range(n_pos):
    acc *= x

It has time complexity \(O(|n|)\), so it times out on large inputs like n = 2147483647.

The fix is to use exponentiation by squaring, which reduces the number of multiplications to \(O(\log |n|)\).

## Solution

import math

math.pow(2.1, 3) # 9.261000000000001

# Time Limit Exceeded - 294 / 307 testcases passed
# time out with input (0.00001, 2147483647)
class Solution:
    def myPow(self, x: float, n: int) -> float:
        n_pos = abs(n)
        acc = 1
        for _ in range(n_pos):
            acc *= x
        return acc if n > 0 else 1 / acc

Solution().myPow(2.1, 3) # 9.261000000000001
Solution().myPow(2.0, -2) # 0.25
math.pow(0.00001, 2147483647) # 0.0
Solution().myPow(0.00001, 2147483647) # time out

Extra¶

2 examples of power decomposition¶