Pow(x, n) medium

Problem Statement

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

Example 1:

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

Example 2:

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

Steps & Explanation

The naive approach of iteratively multiplying x by itself n times is inefficient for large values of n. A much more efficient approach is to use recursion and binary exponentiation.

Binary exponentiation leverages the following property:

xn = (xn/2)2 if n is even xn = x * (x(n-1)/2)2 if n is odd

This allows us to compute xn in logarithmic time, significantly faster than the linear time of the naive approach. We handle negative exponents by taking the reciprocal of the result for the positive exponent.

  1. Handle Base Cases: If n is 0, return 1 (x0 = 1). If n is negative, handle it by calculating the positive exponent and taking the reciprocal.

  2. Recursive Calculation: If n is even, recursively calculate xn/2 and square the result. If n is odd, recursively calculate x(n-1)/2, square the result, and multiply by x.

  3. Return Result: Return the calculated value.

Code

function myPow(x: number, n: number): number {
    if (n === 0) return 1;
    if (n < 0) return 1 / myPow(x, -n); // Handle negative exponents

    if (n % 2 === 0) {
        const halfPower = myPow(x, n / 2);
        return halfPower * halfPower;
    } else {
        const halfPower = myPow(x, (n - 1) / 2);
        return x * halfPower * halfPower;
    }
};

Complexity Analysis

  • Time Complexity: O(log n). The recursive calls reduce the exponent by approximately half in each step, leading to logarithmic time complexity.

  • Space Complexity: O(log n). This is due to the recursive call stack. In the worst case, the depth of the recursion is proportional to the logarithm of n. This could be improved to O(1) by using an iterative approach instead of recursion. However, the recursive approach is arguably more readable.

An iterative solution (for O(1) space complexity) would look like this:

function myPowIterative(x: number, n: number): number {
    if (n === 0) return 1;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    let result = 1;
    while (n > 0) {
        if (n % 2 === 1) result *= x;
        x *= x;
        n = Math.floor(n / 2);
    }
    return result;
}

Both solutions achieve the same time complexity, but the iterative one uses constant space. Choose the one that best suits your needs in terms of readability and space optimization priorities.