The problem of calculating xn, where x is a double and n is an integer, can be efficiently solved using a recursive approach known as exponentiation by squaring. This method significantly reduces the number of multiplications required compared to a naive iterative approach.

Function Signature The core of the solution is a function that takes a base x (a double) and an exponent n (an integer) and returns the result x^n as a double.

double calculatePower(double base, int exponent) {
    // Implementation details follow
}

Base Cases The recursion needs base cases to termintae.

If the exponent `n` is 0, any non-zero base `x` raised to the power of 0 is 1.
If the exponent `n` is 1, `x` raised to the power of 1 is simply `x`.

if (exponent == 0) {
    return 1.0;
}
if (exponent == 1) {
    return base;
}

Handling Negative Exponents A negative exponent n implies calculating the reciprocal of the base raised to the positive exponent. That is, xn = 1 / x-n. A critical edge case arises when n is the minimum value for a 32-bit signed integer (-2147483648). Directly negating this value would result in integer overflow. To circumvent this, we can rewrite it as 1 / (x-(n+1) * x).

if (exponent < 0) {
    if (exponent == -2147483648) { // Special handling for INT_MIN
        return 1.0 / (calculatePower(base, -(exponent + 1)) * base);
    }
    return 1.0 / calculatePower(base, -exponent);
}

Recursive Step for Even Exponents If the exponent n is even, we can leverage the property xn = (xn/2)2. This allows us to halve the problem size in each recursive step. We calculate x^(n/2) once and then square the result.

if (exponent % 2 == 0) {
    double halfPower = calculatePower(base, exponent / 2);
    return halfPower * halfPower;
}

Recursive Step for Odd Exponents If the exponent n is odd, we can express xn as x * xn-1. Since n-1 is even, we can apply the logic for even exponents to x^(n-1). Alternatively, and more commonly in this algorithm, we can write it as x * (x(n-1)/2)2. This is equivalent to calculating x^((n-1)/2), squaring it, and then multiplying by x.

else { // exponent is odd
    double halfPower = calculatePower(base, exponent / 2); // Integer division naturally handles (n-1)/2
    return halfPower * halfPower * base;
}

This recursive structure effectively breaks down the exponentiation problem into smaller, manageable subproblems, leading to an efficient solution.

Time Complexity The time complexity is determined by the number of recursive calls. In each step, the exponent is roughly halved. This logarithmic reduction in the problem size leads to a time complexity of O(log |n|).

Space Complexity The space complexity is dictated by the depth of the recursion call stack. In the worst-case scenario (handling the minimum integer value for the exponent), the depth can approach |n|. However, for typical inputs and the balanced nature of the exponent halving, the average space complexity is O(log |n|).

The overall implementation, considering all cases, results in an efficient algorithm for calculating powers with a logarithmic time complexity.

class Solution {
public:
    double calculatePower(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }

        if (n < 0) {
            // Handle the edge case of the minimum integer value to avoid overflow
            if (n == -2147483648) {
                return 1.0 / (calculatePower(x, -(n + 1)) * x);
            }
            return 1.0 / calculatePower(x, -n);
        }

        double halfPow = calculatePower(x, n / 2);
        if (n % 2 == 0) {
            return halfPow * halfPow;
        } else {
            return halfPow * halfPow * x;
        }
    }
};