Gyh's Braindump

CN-16. Power of x

tags
Recursion, FME
source
leetcode-cn

Edge Cases

  1. when number is negative min value

    • 1 / pow(x, -(n + 1)) * 1 / x
    • or convert n to long type

  2. when base is 0 and number is negative

Solution 1 - FME

class Solution {
    public double myPow(double x, int n) {
        if (n < 0) {
            if (x == 0) return Double.POSITIVE_INFINITY;
            else return 1 / myPow(x, -(n + 1)) * 1 / x;
        }
        double res = 1;
        while (n != 0) {
            if ((n & 1) == 1) {
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

Complexity

  • time: O(lgN)
  • space: O(1)

Solution 2 - Recursion

class Solution {
    public double myPow(double x, int n) {
        if (n < 0) {
            if (x == 0) return Double.POSITIVE_INFINITY;
            else return 1 / myPow(x, -(n + 1)) * 1 / x;
        }
        if (n == 0) return 1;
        return n % 2 == 1 ? x * myPow(x, n - 1) : myPow(x * x, n >> 1);
    }
}