LeetCode 50 - Pow(x, n)

Implement pow(x, n).

Solution 1:

Recursive

public double pow(double x, int n) {
    if(n == 0) return 1;
    if(n == 1) return x;
    boolean negate = n < 0;
    if(negate) n = -n;
    int k = n / 2;
    double val = pow(x, k);
    double result = val * val * pow(x, n-k*2);
    return negate ? 1/result : result;
}

 

Solution 2:

iterative.

/* Iterative Function to calculate x raised to the power y in O(logy) */
int power(int x, unsigned int y) {
    // Initialize result
    int res = 1;
 
    while (y > 0) {
        // If y is even, simply do x square
        if (y%2 == 0) {
            y = y/2;
            x = x*x;
        } else {
            // Else multiply x with result.  Note that this else 
            // is always executed in the end when y becomes 1   
            y--;
            res = res*x;
        }
    }
    return res;
}