[LeetCode] 50. Pow(x, n)

Implement pow(x, n).


Sol. Divide the number into two smaller numbers. Corner case need extra attention. Integer range is [–2,147,483,648, 2,147,483,647]. Divide 2 before turning negative n to positive to avoid overflow.

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

    }

Time Complexity: O(logn)
Space Complexity: O(1)