Python solution with cache beating 98.06%


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

  • 0
    T

    That's smart. I used to choose [None]*(n+2) instead of dictionary as the memo table, but obvious it wasted too much space that reached memory limit.


Log in to reply
 

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