50. Pow(x, n).md

50. Pow(x, n)

---

leetcode Daily Challenge on July 16th, 2020.

---

Difficulty : Medium

Related Topics : Math、BinarySearch

---

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

---

Solution

• mine
  • Java
    • Runtime: 1 ms, faster than 46.27%, Memory Usage: 39.9 MB, less than 5.01% of Java online submissions

      // O(logN)time
      // O(logN)space
      public double myPow(double x, int n) {
          if(n == 0 || x == 1){
              return 1;
          }
          if(x == -1){
              return (n & 1) == 0 ? 1 : -1;
          }
          int t = Math.abs(n / 2);
          double res = (n & 1) == 0 ? myPow(x * x, t) :  x * myPow(x * x, t);
          return n > 0 ? res : 1.0 / res;
      }
      

---

• leetcode solution

  • Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.5 MB, less than 75.25% of Java online submissions

    // O(logN)time
    // O(logN)space
    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
    
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
    

  • Runtime: 1 ms, faster than 46.27%, Memory Usage: 36.8 MB, less than 47.48% of Java online submissions

    // O(logN)time
    // O(1)space
    double quickMul(double x, long N) {
        double ans = 1.0;
        double x_contribute = x;
        while (N > 0) {
            if (N % 2 == 1) {
                ans *= x_contribute;
            }
            x_contribute *= x_contribute;
            N /= 2;
        }
        return ans;
    }
    
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
    

---

---