[LeetCode 50] Pow(x, n)

Question

link

Implement pow(x, n).

Stats

Frequency	5
Difficulty	3
Adjusted Difficulty	3
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This question have many interesting solutions. The bottom line is solving in O(lgn) time.

First approach, we can keep cumulating power(x, 2 ^ n).

Second approach, divide and conquer which is explained in this blog and this code.

Read code below.

My code

code 1, divide and conquer

public class Solution {
    public double pow(double x, int n) {
        if (n == 0) {
            return 1;
        } else if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                // since the negate of Integer.MIN_VALUE overflows...
                return (1 / x) / pow(x, Integer.MAX_VALUE);
            } else {
                return 1 / pow(x, -1 * n);
            }
        } else if (n % 2 == 0) {
            return pow(x * x, n / 2);
        } else {
            return x * pow(x, n - 1);
        }
    }
}

code 2, divide and conquer

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

private double helper(double x, int n) {
    if (n == 0) return 1;
    double half = helper(x, n / 2);
    return n % 2 == 1 ? x * half * half : half * half;
}

code 3

public double pow(double x, int n) {
    if (n == 0) return 1;
    if (n == 2) return x * x;

    if (n % 2 == 0) return pow(pow(x, n / 2), 2);
    else if (n > 0) return x * pow(pow(x, n / 2), 2);
    else return 1 / x * pow(pow(x, n / 2), 2);
}