Pow(x, n) medium

Problem Statement

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

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⁻² = 1/2² = 1/4 = 0.25

Steps and Explanation

The naive approach of iteratively multiplying x by itself n times is inefficient for large values of n. A much more efficient approach utilizes recursion and the concept of exponentiation by squaring.

The core idea is based on the following mathematical property:

xⁿ = (x^n/2)² if n is even xⁿ = x * (x^(n-1)/2)² if n is odd

We recursively calculate x^n/2 or x^(n-1)/2, square the result, and optionally multiply by x (if n is odd). This significantly reduces the number of multiplications needed. We handle negative exponents by taking the reciprocal of the positive exponent result.

We also need to handle the edge case where n is 0 (x⁰ = 1) and consider potential integer overflow issues, especially with negative n.

Code (Python)

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

        half_pow = self.myPow(x, n // 2)  # Recursive call for half the exponent

        if n % 2 == 0:
            return half_pow * half_pow  # Even exponent
        else:
            return x * half_pow * half_pow  # Odd exponent

Complexity Analysis

• Time Complexity: O(log n). The recursive approach halves the exponent in each step, resulting in a logarithmic time complexity.
• Space Complexity: O(log n). The space complexity is determined by the recursive call stack depth, which is also logarithmic due to the halving of the exponent in each step. In iterative solutions, the space complexity is O(1).

Alternative Iterative Solution (O(1) space):

A more space-efficient solution can be achieved iteratively using a while loop:

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

        res = 1.0
        while n > 0:
            if n % 2 == 1:
                res *= x
            x *= x
            n //= 2
        return res

This iterative version achieves the same time complexity (O(log n)) but with constant space complexity O(1). It directly implements the exponentiation by squaring without the overhead of recursive function calls.