50. Pow(x, n)

Intuition

To compute xⁿ, a brute-force approach multiplying x by itself n times would take O(n) time, which is inefficient for large n. Instead, we use Exponentiation by Squaring, which reduces the time complexity to O(log n).

This works by repeatedly squaring x and halving n.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

// Recursive helper function for exponentiation
public double powerHelper(double base, long exponent) {
    // Handle negative exponent by flipping base and making exponent positive
    if (exponent < 0) return powerHelper(1 / base, -exponent);

    // Quick returns for common base cases
    if (base == 1) return 1;
    if (base == -1) return (exponent & 1) == 1 ? -1 : 1;

    // Base case: anything raised to 0 is 1
    if (exponent == 0) return 1;

    // Base case: power of 1
    if (exponent == 1) return base;

    // Special case: power of 2
    if (exponent == 2) return base * base;

    // Recursive case using exponentiation by squaring
    return (exponent & 1) == 1
        ? base * powerHelper(base * base, (exponent - 1) / 2)
        : powerHelper(base * base, exponent / 2);
}

// Public method called with the given inputs
public double myPow(double base, int exponent) {
    return powerHelper(base, exponent);
}