50. Pow(x, n)

Implement pow(x, n).



Solution:

Method 1: Recursive

If n == 0, we return 1.

We first calculate x^n/2. This actually help to deal with n = Integer.MIN_VALUE to prevent overflow. Let's say pow = x^n/2.

If n can be divided by 2, we simply return the product of the above pow result.

If we find n < 0, we need multiply the left x^-1, which results pow * pow / x.

If we find n > 0, we simply return pow * pow * x.



Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double pow = myPow(x, n / 2);
        if (n % 2 == 0) {
            return pow * pow;
        }
        return (n < 0) ? pow * pow / x : pow * pow * x;
    }
}

Method 2: Iterative

a^b = (a²)^b/2, b is even
a^b = (a²)^b/2 x a, b is odd

The time complexity is O(logn) and the space complexity is O(1)



Code:

public class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        long absN = Math.abs((long) n);
        while (absN > 0) {
            if (absN % 2 == 1) {
                res *= x;
            }
            absN /= 2;
            x *= x;
        }
        return n < 0 ? 1.0 / res : res;
    }
}