50. Pow(x, n)

Problem¶

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

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/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n is an integer.
• Either x is not zero or n > 0.
• -10**4 <= xn <= 10**4

Solve¶

Use built-in function¶

O(log n)

class Solution(object):
    def myPow(self, x, n):
        return pow(x,n)
        # return x ** n

double myPow(double x, int n){
     return pow(x,n);
}

Actually doing some thing¶

Basically, we can use the following recursive formula to calculate x^n efficiently:
pow(x,n) = pow(x,n/2) * pow(x,n/2) * pow(x,n%2)

python¶

O(log n)

There isn’t anything stop python from working

• Implement the function directly using recursion

• Case n < 0: we just need to change our x = 1/x and can safely clear n sign; Keep in mind that when x == 0, this can throw error.
  

  class Solution:
      def myPow(self, x: float, n: int, cache = None) -> float:
          if n ==0 :
              return 1
          if n <0 :
              return self.myPow(1/x,-n)
          if n%2 == 0:
              return self.myPow(x, n//2) **2
          else:
              return x * self.myPow(x,n//2)**2
  

• The above code could re-calculate some pow(), to avoiding this, we can add a cache array.
  

  class Solution:
      def myPow(self, x: float, n: int, cache = None) -> float:
          if x == 0.:
              return 0
  
          if cache is None:
              cache = {}
              cache[0] = 1.
              cache[1] = x
              if x != 0:
                  cache[-1] = 1./x
  
          if n in cache:
              return cache[n]
  
          cache[n] = self.myPow(x, n//2, cache) * self.myPow(x, n//2, cache)* self.myPow(x, n%2, cache)
          return cache[n]
  

C language¶

O(1)

Using the same logic, but there is some thing to consider:

• We can’t just revert the sign of a number, as int value have 32 bit, which MAX_INT == 2**31 and MIN_INT == 2**31 - 1 (because of 0)
• C not have dict() by default and we also don’t want to create a large [-2*32..2*32-1] array. While this can be overcome with Hash functions, we can store only [x**(2**0), x**(2**1), ..., x**(2**32)]
• A number n is presented using binary; which mean, by using bit manipulation, we can easily split-ed n to sum of = (1 or 0) * 2**0 + (1 or 0) * 2**1 + ... + (1 or 0) 2 ** 32. Leverage: x**n = x ** (<splited number which total = n>). We can using this binary split instead of divine by 2 like python.

• Here is the Try to match Python function
  

  double cache[32];
  
  double myPow(double x, int n){
      long tmp_n = n;
      if (x == 0.)
          return 0;
      if (tmp_n < 0) {
          tmp_n = -tmp_n;
          x = 1./x;
      }
      cache[0] = x;
      double answer = 1.;
      for (int i = 0; i < 32 || tmp_n > 0; i++) {
          bool flag = tmp_n & 1;
          tmp_n = tmp_n >> 1;
          if (i > 0)
              cache[i] = cache[i-1] * cache[i-1];
          if (flag)
              answer *= cache[i];
      }
      return answer;
  }
  

• As we only need cache[i-1], we not even need cache in the fist place;

• The way to handle n < 0 can be optimize more, instead of large the variable with 64 bit long integer.
  • In C, negative number is representing in ~ <unsign> +1, which mean flipping all bit in unsigned number and then plus 1 (example 0001 become 1110 + 1 = 1111)
  • We can use this instead of n = -n bit flip which could result an out of memory scope error.
  • We handle the separated plus 1 directly in case of n < 0
    

    double myPow(double x, int n){
        if (x == 0.)
            return 0;
    
        double answer = 1.;
        bool flag = n < 0;
        if (flag) {
            answer /= x;
            n = ~n;
        }
    
        for (;;) {
            if (n & 1) {
                if (flag)
                    answer /= x;
                else
                    answer *= x;
            }
            n = n >> 1;
            if (!n)
                break;
            x = x * x;
        }
        return answer;
    }
    

Or this, separating n == 0; n > 0; and n < 0 also work:

double myPow(double base, int exp)
{
    double result = 1;
    if (base == 0) return 0;
    if (exp > 0)
        for (;;) {
            if (exp & 1)
                result *= base;
            exp >>= 1;
            if (!exp)
                break;
            base *= base;
        }
    else if (exp < 0) {
        exp = ~(exp);
        result /= base;
        for (;;) {
            if (exp & 1)
                result /= base;
            exp >>= 1;
            if (!exp)
                break;
            base *= base;
        }
    }

    return result;
}

Compiler optimized will help us to minimal the Assembly code in any way; Also, using C we can some how have an optimized function that can process on pair with provided standards pow(x,n) built-in the language, which take 0ms to run.

Time complexity:

• This cost a fixed for loop 32 times, which we can consider it as O(1) run time.
• But, we also can consider this O(log n) time, as it could be better in the second implementation.