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:

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;
  }
}

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).