[Leetcode] Pow(x, n)

Implement pow(x, n).
Using D and C. When we calculate n, we could use the result of n/2.

1. If n is even, pow(x, n) = pow(x, n/2) * pow(x, n/2);
2. If n is odd, pow(x, n) = pow(x, n/2) * pow(x, n/2) * x;

When n is negative, we inverse x and make n positive. Be careful if n is the MIN_VALUE, in this case you could not just simply make n positive since you would get a overflow if you still use integer.

    public double pow(double x, int n) {
        if(n == 0)
            return 1;
        if(n < 0) {
            x = 1 / x;
            if(n == Integer.MIN_VALUE)
                return x * pow(x, Integer.MAX_VALUE);
            else
                return pow(x, -n);
        }
        /*double res = 1;
        while(n != 0) {
            if(n % 2 == 1)
                res = res * x;
            x = x * x;
            n = n / 2;
        }
        return res;*/

        double res = pow(x, n/2);
        if(n % 2 == 0)
            return res*res;
        else
            return res*res*x;
    }