MEDIUM

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Example

Input:

x = 2.00000, n = 10

Output:

1024.00000

Explanation:
2^10 = 1024

Constraints

-100.0 < x < 100.0
-2^{31} ≤ n ≤ 2^{31} - 1
n is an integer.
Either x is not zero or n > 0.
-10^4 ≤ x^n ≤ 10^4

Solution: Fast Power (Recursion)

Time Complexity: O(log n)
Space Complexity: O(log n)

C++

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
private:
    double fastPow(double x, long long n) {
        if (n == 0) return 1.0;
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) return half * half;
        else return half * half * x;
    }
};