Pow(x, n)

LeetCode https://leetcode.cn/problems/powx-n/

class Solution {

    public double myPow(double x, int n) {

        if (x == 0 && n <= 0) {
            return -1;
        } else if (n < 0) {
            return 1.0 / myPowHelper(x, -n);
        } else {
            return myPowHelper(x, n);
        }
    }

    private double myPowHelper(double x, int n) {

        // base case
        if (n == 0) {
            return 1;
        }

        double halfResult = myPowHelper(x, n/2);

        if (n % 2 == 0) {
            return halfResult * halfResult;
        } else {
            return halfResult * halfResult * x;
        }
    }
    
}

Complexity

• Time = O(log(n))
• Space = O(log(n))

---