Pow(x, n)

Implement pow(x, n).

Example:

Pow(2.1, 3) = 9.261

Pow(0, 1) = 0

Pow(1, 0) = 1

Challenge:

O(logn) time.

Solution:

x^n = x^{n\/2} * x^{n\/2} * x^{n%2}.

Code:

public double myPow(double x, int n) {
    if (n < 0) {
        return 1 / helper(x, -n);
    }
    return helper(x, n);
}

private double helper(double x, int n) {
    if (n == 0) {
        return 1;
    }
    double v = helper(x, n / 2);
    if ((n & 1) == 0) {
        return v * v;
    } else {
        return v * v * x;
    }
}