Pow(x, n)

Implement pow(x, n).

/*
The naive way is to use a for loop to multiply x every time. 
time:O(n), space:O(1)

The better way is to use divide & conquer, cut n to half from every recursion.
Be careful when n = Integer.MIN_VALUE, if directly set n = -n, it will be wrong due to out of Integer range. So we can do some transformation, let it be x / x^(-(n + 1)), when n < 0.

time:O(logn), space:O(1)
*/

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            double ans = x * myPow(x, -(n + 1));
            return 1.0 / ans;
        }
        
        double t = myPow(x, n / 2);
        return n % 2 == 0 ? t*t : x*t*t;
    }

}