Pow(x, n) — Day 68(Python)

Photo by Amritanshu Sikdar on Unsplash

Today’s question is a favorite question among Facebook interviewers. Let us look into the question.

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

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

We can solve the given problem using recursion.

Since we are using recursion, we need to identify the base condition. What is the minimum valid input? It is when n is equal to 0. When n = 0, the power of that number is 1.

if n == 0:
   return 1

We can notice that “n” can be negative too. What do we do in such a case? We will find the power of the reciprocal of that number.

if n < 0:
   return(self.myPow(1/x, n*-1))

The recursive call will be as follows.

else:
   return x * self.myPow(x, n-1)

Let us look into the complete code snippet.

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

Complexity analysis.

Time Complexity

We are calling the recursive function for “n” times. Hence the time complexity is O(n).

Space Complexity.

We are calling the recursive function for “n” times. Internally recursive calls are stored in a stack. Hence the space complexity is O(n).

If we try to run this program, we will either get maximum recursion reached or the time limit exceeded. How can we try to improve?

We will try solving it in a step by step approach.

We can use two myPow functions and multiply both of them together. Does it sound confusing? Let us look at how it would look like in code.

return self.myPow(x, n//2) * self.myPow(x, n//2)

But we need to keep in mind that the above code can run only when n is even. What about cases when n is odd? Then we need to make it even. How do we do that?

return x * self.myPow(x, n-1)

Let us look at the complete code snippet.

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

If we run this code, we might still get maximum recursion reached or the time limit exceeded. How can we try to improve? Memoization is the answer.

In this case, “n” keeps changing each time. Hence we will have to memoization this value. We can use a dictionary to store the results. Let us look at how we can use memoization and solve this problem.

class PowFinder:
    def __init__(self):
        self.dict_pow = dict()
        
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            return self.myPow(1/x, n*-1)
        if n in self.dict_pow:
            return self.dict_pow[n]
        if n == 0:
            return 1
        elif n%2 == 0:
            self.dict_pow[n] = self.myPow(x, n//2) * self.myPow(x, n//2)
            return self.dict_pow[n]
        else:
            self.dict_pow[n] =  x * self.myPow(x, n-1)
            return self.dict_pow[n]

Complexity analysis.

Time Complexity

We are calling the recursive function for “n/2” times. Hence the time complexity is O(logn).

Space Complexity.

We are calling the recursive function for “n/2” times. Internally recursive calls are stored in a stack. Hence the space complexity is O(logn).