Implement pow(x, n).

You don’t need to care about the precision of your answer, it’s acceptable if the expected answer and your answer ‘s difference is smaller than 1e-3.

Example

x      n    pow(x, n)
2.1    3    9.261
0      1    0
1      0    1

The following implements the exponentiation by squaring algorithm, which is described here.

public class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if(x == 1) return 1;
        if(x == -1) {
            if(n % 2 == 0) return 1;
            else return -1;
        }

        if(n < 0) //n is negative
            return myPow(1 / x, -n);

        if(n % 2 == 0) //if n is even
            return myPow(x * x, n / 2);
        else           //if n is odd
            return x * myPow(x * x, (n - 1) / 2);
    }
}