Question:

Implement pow(x, n).

Thinking:

It’s a simple but not simple question. There are many solutions for this problem. But how can we find the most effienct one. We can use recursion to reduce the times of multipling and check the bound of data to reduce the times of recursions. Finally, the code is below:

static boolean negflag = false;
public double myPow(double x, int n) {
    if (n < 0){
        negflag = true;
        return 1 / dp(x, -n);
    }
    else
        return dp(x, n);

}
private double dp(double x, int n){
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    if (n == 2)
        return x * x;

    int m = n / 2;
    int k = n % 2;
    double v = dp(x, m);
    if (negflag == true && v > 100000)
        return 100000;
    if (negflag == false && v < 0.00001)
        return 0;

    if (k == 0)
        return v * v;
    else
        return v * v * x;
}

By the way, I have to metion that my python solution is like, lol:

def myPow(self, x, n):
    return x**n