Leetcode: Pow(x,n)

Implement pow(x, n)

Solution:

We can do this problem in O(log n) by applying $X^n =X^{n/2}\cdot X^{n/2}$ or $X^n =X^{(n-1)/2}\cdot X^{(n-1)/2} \cdot X$ if $n$ is odd.

public class Solution {
    public double pow(double x, int n) {
        if(x==1 || x==0)
            return x;
        if(x==-1)
            return (n%2)==0?1:-1;
        if (n==0)
            return 1;
        if (n==1)
            return x;
        if(n<0)
            return 1/pow(x,-n);
        double val = pow(x,n/2);
        return (n%2)==0 ? val*val  : val*val*x;
    }
}