Pow(x, n)

Problem

Implement pow(x, n).

Solution

Recursive Solution

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (x == 0) return 0;
        if (n < 0) {
            x = 1 / x;
            if (n == Integer.MIN_VALUE) {
                n++;
                x *= x; //avoid overflow when changing -2....8 to 2....7
            } 
            n = -n;
        }
        return n % 2 == 0 ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
    }
}

Analysis

A typical recursive solution
Check some corner cases at the beginning
Then handle the situation where n < 0
Notice that to avoid overflow when changing Integer.MIN_VALUE to 2....8
At the end, recursively call the function depending on n % 2 cause result of n / 2 will be smaller when n is odd