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

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2<sup>-2</sup> = 1/2<sup>2</sup> = 1/4 = 0.25

Steps and Explanation

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

The key idea is to break down the power calculation into smaller subproblems. For example:

x¹⁰ = (x⁵)² x⁵ = x² * x² * x x² = x * x

Notice that we are repeatedly halving the exponent (n) and squaring the base (x). This drastically reduces the number of multiplications needed.

We handle negative exponents by calculating the reciprocal of the positive exponent result. We also need to handle the edge case of n being 0, which results in 1.

Code (Java)

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            x = 1 / x;
            n = -n; // Handle negative exponents
        }
        return fastPow(x, n);
    }

    private double fastPow(double x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        double halfPow = fastPow(x, n / 2); // Recursive call for half the exponent
        if (n % 2 == 0) {
            return halfPow * halfPow; // Even exponent: square the half power
        } else {
            return halfPow * halfPow * x; // Odd exponent: square the half power and multiply by x
        }
    }
}

Complexity Analysis

• Time Complexity: O(log n). The recursive fastPow function halves the exponent in each call, resulting in logarithmic time complexity.

• Space Complexity: O(log n). The space complexity is determined by the depth of the recursion stack, which is proportional to log n. In practice, tail-call optimization might reduce this to O(1) in some compilers/interpreters. However, Java doesn't have tail-call optimization, so we should consider it O(log n).