Thinking process

how to calculate pow faster

• 2^3 = 2 * 2 * 2 = 4^1 * 2
• 2^5 = 4^2 * 2

Mistakes

• n could be negative, how to handle negative input?
• 2^-3 = 1/2 * 1/2 * 1/2 = 1/2 ^ 3

Version I -- double x

when n = Integer.MIN_VALUE, n = -n will overflow

It has a minimum value of -2,147,483,648 and a maximum value of 2,147,483,647

http://stackoverflow.com/questions/15004944/max-value-of-integer

public class Solution {
    public double myPow(double x, int n) {
        if(n==0) return 1;
        if(n<0){
            if (n == Integer.MIN_VALUE) {
                n = Integer.MAX_VALUE;
                x = 1/x;
                return x * x * myPow( x*x, n/2 );
            } else {
                n = -n;
                x = 1 / x;
            }
        }
        return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
    }
}