Pow(x, n)

Problem Statement

Pow(x, n) is a mathematical function to calculate the value of x raised to the power of n (i.e., x^n).

Given a floating-point value x and an integer value n, implement the myPow(x, n) function, which calculates x raised to the power n.

You may not use any built-in library functions.

Example 1:

Input: x = 2.00000, n = 5
Output: 32.00000

Example 2:

Input: x = 1.10000, n = 10
Output: 2.59374

Example 3:

Input: x = 2.00000, n = -3
Output: 0.12500

Constraints:

• -100.0 < x < 100.0
• -1000 <= n <= 1000
• n is an integer.
• If x = 0, then n will be positive.

Recommended Time and Space Complexity

Aim for a solution with O(log n) time complexity.

Hint 1

Consider using a divide-and-conquer approach.

Hint 2

Think about how to handle negative exponents.

Hint 3

Binary exponentiation can significantly improve efficiency.

Solution

Brute Force

def my_pow_brute_force(x: float, n: int) -> float:
    if x == 0:
        return 0
    if n == 0:
        return 1

    res = 1
    for _ in range(abs(n)):
        res *= x
    return res if n >= 0 else 1 / res

Time complexity: O(n) Space complexity: O(1)

Binary Exponentiation (Recursive)

def my_pow_recursive(x: float, n: int) -> float:
    def helper(x, n):
        if x == 0:
            return 0
        if n == 0:
            return 1

        res = helper(x * x, n // 2)
        return x * res if n % 2 else res

    res = helper(x, abs(n))
    return res if n >= 0 else 1 / res

Time complexity: O(log n) Space complexity: O(log n)

Binary Exponentiation (Iterative)

def my_pow_iterative(x: float, n: int) -> float:
    if x == 0:
        return 0
    if n == 0:
        return 1

    res = 1
    power = abs(n)

    while power:
        if power & 1:
            res *= x
        x *= x
        power >>= 1

    return res if n >= 0 else 1 / res

Time complexity: O(log n) Space complexity: O(1)