Pow(x, n)

---

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

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

---

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

---

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

---

Constraints:

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• n is an integer.
• -10^4 <= x^n <= 10^4

---

Try this Problem on your own or check similar problems:

1. Sqrt(x)
2. Super Pow

Solution:

Java

class Solution {
  public double myPow(double x, int n) {
      if(n == 0) return 1.0;
      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 halfPow = pow(x, n / 2);
      if(n % 2 == 0){
          return halfPow * halfPow;
      }
      return halfPow * halfPow * x;
  }
}

JavaScript

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  if (n === 0) return 1.0;
  if (n < 0) return 1.0 / pow(x, -n);
  return pow(x, n);
};

function pow(x, n) {
  if (n === 0) return 1;
  var halfPow = pow(x, Math.floor(n / 2));
  if (n % 2 === 0) {
    return halfPow * halfPow;
  }
  return halfPow * halfPow * x;
}

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0 / self.pow(x, -n)
        return self.pow(x, n)

    def pow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        half_pow = self.pow(x, n // 2)
        if n % 2 == 0:
            return half_pow * half_pow
        return half_pow * half_pow * x

C++

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0)
            return 1.0;
        if (n < 0)
            return 1.0 / pow(x, static_cast<long long>(n) * -1);
        return pow(x, n);
    }

private:
   double pow(double x, long long n) {
        if (n == 0)
            return 1;
        double halfPow = pow(x, n / 2);
        if (n % 2 == 0) {
            return halfPow * halfPow;
        }
        return halfPow * halfPow * x;
    }
};

---

Time/Space Complexity:

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

---

Explanation:

The time and space complexity is logarithmic since we can ask ourselves how many times can we half n (it's logn times), space complexity accounts for the recursion stack. The base case is if n=0 we know that x^0=1 so we return 1. For negative numbers we calculate the reciprocate value since x^-y = 1/x^y. Note that we can formulate recursive relation for pow operation pow(x, n) = pow(x^n/2) * pow(x^n/2) for even n (e.g. x^4 = x^2 * x^2), while for odd n we have the following pow(x, n) = pow(x^n/2) * pow(x^n/2) * x (e.g. x^5 = x^2 * x^2 * x).