Pow (x ^ N) [FastPow recursion)

50.Pow(x, n)

Math

Recursion

Divide and Conquer

Problem Statement:

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Handle negative powers and potential overflow cases.

Example:

Input:

x = 2.00000, n = 10

→

Output:

1024.00000

2^10 = 1024

Algorithm:

1. Handle negative powers by using reciprocal
2. Use recursion to divide power by 2
3. Handle even and odd powers separately
4. Use long to avoid integer overflow

Complexity:

Time: O(log n) | Space: O(log n) for recursion stack

Java Solution:

public double myPow(double x, int n) {
    // Convert to long to handle MIN_VALUE case
    long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    
    return fastPow(x, N);
}

private double fastPow(double x, long n) {
    // Base case: x^0 = 1
    if (n == 0) return 1d;
    
    // Calculate half power recursively
    double half = fastPow(x, n / 2);
    
    // Even power: use x^n = (x^(n/2))^2
    if (n % 2 == 0) 
        return half * half;
    // Odd power: multiply by extra x
    else
        return half * half * x;
}

Python Solution:

def myPow(self, x: float, n: int) -> float:
    def fastPow(x: float, n: int) -> float:
        # Base case: x^0 = 1
        if n == 0:
            return 1
        
        # Calculate half power recursively
        half = fastPow(x, n // 2)
        
        # Even power: use x^n = (x^(n/2))^2
        if n % 2 == 0:
            return half * half
        # Odd power: multiply by extra x
        else:
            return half * half * x
    
    # Handle negative powers
    N = n
    if N < 0:
        x = 1 / x
        N = -N
    
    return fastPow(x, N)

C++ Solution:

double myPow(double x, int n) {
    // Convert to long to handle MIN_VALUE case
    long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    
    return fastPow(x, N);
}

double fastPow(double x, long n) {
    // Base case: x^0 = 1
    if (n == 0) return 1.0;
    
    // Calculate half power recursively
    double half = fastPow(x, n / 2);
    
    // Even power: use x^n = (x^(n/2))^2
    if (n % 2 == 0)
        return half * half;
    // Odd power: multiply by extra x
    else
        return half * half * x;
}