Python top-down approach. Memoization saves hundreds of ms (345ms -> 36ms).


  • 3
    W

    First recursive solution without memo: 345ms

    class Solution(object):
        def integerReplacement(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 1:
                return 0
            if n % 2:
                return 1 + min(self.integerReplacement(n+1), self.integerReplacement(n-1))
            else:
                return 1 + self.integerReplacement(n/2)
    

    Write a helper function with memo: 36ms

    class Solution(object):
        def integerReplacement(self, n):
            """
            :type n: int
            :rtype: int
            """
            memo = {1:0}
            return self.recRep(n, memo)
            
        def recRep(self, n, memo):
            if n in memo:
                return memo[n]
            if n % 2:
                memo[n] = 1 + min(self.recRep(n+1, memo), self.recRep(n-1, memo))
                return memo[n]
            else:
                memo[n] = 1 + self.recRep(n/2, memo)
                return memo[n]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.