[LeetCode] 50. Pow(x, n)

Problem : https://leetcode.com/problems/powx-n/description/

Use memorization to save result from previous calculation

Time Complexity :  O( Log(n) )

class Solution(object):
    class Solution:
    def myPow(self, x: float, n: int) -> float:
        
        @lru_cache(maxsize = None)
        def helper(i):
            if i == 0:
                return 1
            
            if i == 1:
                return x
            
            return helper(i//2) * helper(i//2) * helper(i % 2)
        
        return helper(n) if n >= 0 else 1 / helper(-1 * n)

Another recursive solution:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1

        if n == 1:
            return x
        
        positive = True
        
        if n < 0:
            positive = False
            n *= -1
            
        result = self.myPow(x, n // 2)
        result *= result
        
        if n % 2:
            result *= x
        
        return result if positive else 1 / result