# 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)**.<br>

This works by repeatedly squaring `x` and halving `n`.

## Complexity

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

## Code

```java
// 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);
}

```