Power of a Number (x^n)

Problem Statement

Calculate x raised to the power n (x^n), where x is a real number and n is an integer. This medium-level problem showcases recursion with a twist: instead of naively multiplying x n times, use the divide-and-conquer approach (x^n = x^(n/2) × x^(n/2)) to optimize performance. Handle positive, negative, and zero exponents—perfect for mastering recursive efficiency!

Example

Input: x = 2.0, n = 10

Output: 1024.0 (2^10 = 1024)

Input: x = 2.1, n = 3

Output: 9.261 (2.1 × 2.1 × 2.1 ≈ 9.261)

Input: x = 2.0, n = -2

Output: 0.25 (2^-2 = 1 / 2^2 = 0.25)

Code

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0; // Base case
        if (n < 0) return 1.0 / myPow(x, -n); // Handle negative exponents
        
        double half = myPow(x, n / 2); // Recursive step
        if (n % 2 == 0) {
            return half * half; // Even exponent
        } else {
            return half * half * x; // Odd exponent
        }
    }
}
            

def my_pow(x, n):
    if n == 0:
        return 1.0  # Base case
    if n < 0:
        return 1.0 / my_pow(x, -n)  # Handle negative exponents
    
    half = my_pow(x, n // 2)  # Recursive step
    if n % 2 == 0:
        return half * half    # Even exponent
    else:
        return half * half * x  # Odd exponent

# Example usage
print(my_pow(2.0, 10))  # 1024.0
print(my_pow(2.1, 3))   # 9.261
print(my_pow(2.0, -2))  # 0.25
            

function myPow(x, n) {
    if (n === 0) return 1.0; // Base case
    if (n < 0) return 1.0 / myPow(x, -n); // Handle negative exponents
    
    let half = myPow(x, Math.floor(n / 2)); // Recursive step
    if (n % 2 === 0) {
        return half * half; // Even exponent
    } else {
        return half * half * x; // Odd exponent
    }
}

// Example usage
console.log(myPow(2.0, 10)); // 1024
console.log(myPow(2.1, 3));  // 9.261
console.log(myPow(2.0, -2)); // 0.25
            

Explanation

• Base Case: If n = 0, return 1, as any number to the power 0 is 1.
• Negative Exponent: Convert to positive by taking the reciprocal (1/x^n).
• Recursive Divide: Compute x^(n/2) once, then square it for even n, or square and multiply by x for odd n.
• Flow Example (x=2, n=4): myPow(2, 4) → half = myPow(2, 2) → half = myPow(2, 1) → half = myPow(2, 0) * 2 = 2 → 2 * 2 = 4 → 4 * 4 = 16.
• Optimization: Halving the problem size each step makes this much faster than linear recursion!

Note