Implement pow(x, n).

public double pow(double x, int n) {
    // Start typing your Java solution below
    // DO NOT write main() function
    boolean positive = n >= 0 ? true : false;

    int nabs = n == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(n);

    double product = n == Integer.MIN_VALUE ? powHelp(x, nabs) * x : powHelp(x, nabs);

    return positive ? product : 1 / product;

}

public double powHelp(double base, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return base;
    }

    double tmp = powHelp(base, n / 2);
    return tmp * tmp * powHelp(base, n % 2);
}

O(logN)

Version with no helper function

public double myPow(double x, int n) {
        if(n==0){
            return 1;
        }
        int n_abs = Math.abs(n);
        if(n_abs==1){
            return n>0?x:1/x;
        }
        double tmp =  myPow(x, n/2);
        return tmp*tmp*myPow(x, n%2);
    }

Share