Pow(x, n)

Problem

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

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

Constraints:

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n is an integer
Either x is not zero or n > 0
-10^4 <= x^n <= 10^4

Solution

Approach 1: Fast Power (Recursive)

The key insight is to use binary exponentiation: x^n = (x^2)^(n/2) when n is even, and x * x^(n-1) when n is odd.

Implementation

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(x, n):
            # Base cases
            if n == 0:
                return 1
            if n == 1:
                return x

            # Recursive case
            if n % 2 == 0:
                # Even power: x^n = (x^2)^(n/2)
                half = helper(x, n // 2)
                return half * half
            else:
                # Odd power: x^n = x * x^(n-1)
                return x * helper(x, n - 1)

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

        return helper(x, n)

Approach 2: Fast Power (Iterative)

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

        result = 1
        current_product = x

        while n > 0:
            # If n is odd, multiply result by current product
            if n % 2 == 1:
                result *= current_product

            # Square the current product
            current_product *= current_product

            # Divide n by 2
            n //= 2

        return result

Approach 3: Binary Representation

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

        result = 1

        while n:
            # If the least significant bit is 1
            if n & 1:
                result *= x
            x *= x
            n >>= 1

        return result

Approach 4: Optimized Recursive

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(x, n):
            if n == 0:
                return 1

            half = helper(x, abs(n) // 2)
            half = half * half

            # If n is odd, multiply by x one more time
            if abs(n) % 2 == 1:
                half = half * x

            return half if n > 0 else 1 / half

        return helper(x, n)

Complexity Analysis

Time Complexity: O(log n), where n is the exponent. Each recursive/iterative step halves n.
Space Complexity: O(log n) for recursive approach (call stack), O(1) for iterative approach.

Key Insights

Binary Exponentiation: Key optimization that reduces O(n) to O(log n) by repeatedly squaring.
Even Power Optimization: x^8 = (x^4)^2 = ((x^2)^2)^2 requires only 3 multiplications instead of 7.
Negative Exponent: x^(-n) = 1 / x^n, so convert to positive and reciprocate.
Bit Manipulation: Each bit in n’s binary representation indicates whether to include that power of x.
Recursive Formula:
- x^n = (x^(n/2))^2 if n is even
- x^n = x * x^(n-1) if n is odd
Iterative vs Recursive: Iterative avoids stack overflow for very large n and uses O(1) space.
Edge Cases: Handle n = 0 (result is 1), n = 1 (result is x), and negative n properly.