LeetCode 50. Pow(x, n)

Question

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

• https://leetcode.com/problems/powx-n/Solution1

class Solution {
    //time complexity logn
    public double myPow(double x, int n) {
        if ( x == 0 || x == 1) return x;
        if (n < 0) return 1 / pow(x, -n);
        return pow(x, n);
    }
    private double pow(double x, int n){
        if (n == 0) return 1;
        double y = pow(x, n / 2);
        if (n % 2 == 0) return y * y;
        else return y * y * x;
    }
}

Complexity:

Time complexity: O( logn)

Space complexity: O(logn)