Code Implementation

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def fast_pow(base, exp):
            if exp == 0:
                return 1
            half = fast_pow(base, exp // 2)
            if exp % 2 == 0:
                return half * half
            else:
                return half * half * base

        if n < 0:
            x = 1 / x
            n = -n
        return fast_pow(x, n)
      

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
private:
    double fastPow(double base, long long exp) {
        if (exp == 0) return 1.0;
        double half = fastPow(base, exp / 2);
        if (exp % 2 == 0) return half * half;
        else return half * half * base;
    }
};
      

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
    private double fastPow(double base, long exp) {
        if (exp == 0) return 1.0;
        double half = fastPow(base, exp / 2);
        if (exp % 2 == 0) return half * half;
        else return half * half * base;
    }
}
      

var myPow = function(x, n) {
    function fastPow(base, exp) {
        if (exp === 0) return 1;
        let half = fastPow(base, Math.floor(exp / 2));
        if (exp % 2 === 0) return half * half;
        else return half * half * base;
    }
    let N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    return fastPow(x, N);
};
      

Problem Description

The "Pow(x, n)" problem asks you to implement a function that calculates x raised to the power n (i.e., xn). You are given:

• A floating-point number x (the base).
• An integer n (the exponent, which can be negative, zero, or positive).

The function should return xn as a double-precision floating-point number. You are expected to handle large positive and negative values of n efficiently and correctly, including edge cases such as n = 0 and n < 0.

Thought Process

At first glance, it might seem natural to compute xn by multiplying x by itself n times. However, this brute-force approach is inefficient, especially for large exponents, since it would require O(n) multiplications. Additionally, we need to handle negative exponents, which require taking the reciprocal of the result.

To optimize, we can use a method called "Exponentiation by Squaring," which reduces the number of multiplications to O(log n) by exploiting the properties of exponents. For example, x8 can be computed as ((x2)2)2, requiring far fewer multiplications.

The key is to recursively or iteratively break down the exponent into halves, squaring the result at each step. This process also naturally handles both even and odd exponents. For negative exponents, we can invert x and make n positive.

Solution Approach

• Handling Negative Exponents: If n is negative, we convert the problem to 1/x raised to -n. This handles cases like x-3 = 1 / x3.
• Base Cases: If n == 0, the result is always 1 (since any number to the power of 0 is 1).
• Exponentiation by Squaring:
  • If n is even, xn = (xn/2)2.
  • If n is odd, xn = (xn//2)2 * x.
• Recursive or Iterative Implementation: We can implement this process recursively (as in the code above), or iteratively using a loop and bit manipulation.
• Overflow and Edge Cases: Since n can be -231, we need to use a larger integer type (like long in Java/C++), to avoid overflow when negating n.

By following this approach, we can compute the result efficiently and handle all edge cases.

Example Walkthrough

Let's walk through the example x = 2.0, n = 10:

1. n is positive, so we proceed directly.
2. First call: myPow(2.0, 10)
3. Since 10 is even, we compute myPow(2.0, 5), then square the result.
4. myPow(2.0, 5) (odd): Compute myPow(2.0, 2), square it, and multiply by 2.0.
5. myPow(2.0, 2) (even): Compute myPow(2.0, 1), square it.
6. myPow(2.0, 1) (odd): Compute myPow(2.0, 0), square it, and multiply by 2.0.
7. myPow(2.0, 0) returns 1 (base case).
8. Back up the call stack:
   • myPow(2.0, 1): 1 * 1 * 2.0 = 2.0
   • myPow(2.0, 2): 2.0 * 2.0 = 4.0
   • myPow(2.0, 5): 4.0 * 4.0 * 2.0 = 32.0
   • myPow(2.0, 10): 32.0 * 32.0 = 1024.0

Thus, 2.010 = 1024.0.

For negative exponents, e.g., x = 2.0, n = -3:

• Convert to x = 1/2.0, n = 3
• Compute as above: 1/2.0 * 1/2.0 * 1/2.0 = 0.125

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(|n|) (since we multiply x by itself |n| times).
  • Space Complexity: O(1) (no extra space needed).
• Optimized (Exponentiation by Squaring):
  • Time Complexity: O(log |n|) (each step halves the exponent).
  • Space Complexity: O(log |n|) for recursive version (due to call stack), or O(1) for iterative version.

The optimized approach is much faster and suitable for very large exponents.

Summary

The Pow(x, n) problem is elegantly solved using Exponentiation by Squaring, which reduces computation from linear to logarithmic time. By handling negative exponents via reciprocals and breaking the problem down recursively, we achieve both correctness and efficiency. This approach is a classic example of transforming a brute-force algorithm into an optimal one by leveraging mathematical properties.