Python solution with cache beating 98.06%

  • 2
    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
                    d[n] = 1 + min(helper(n + 1, d), helper(n - 1, d))
                return d[n]
            d = {1: 0}
            return helper(n, d)

  • 0

    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.