Python 39ms solution - top-down with memoization


  • 0
    A
    class Solution(object):
        def integerReplacement(self, n):
            """
            :type n: int
            :rtype: int
            """
            def helper(n, mem):
                if n in mem.keys():
                    return mem[n]
                m, cnt = n, 0 
                while n % 2 == 0:
                    n //= 2
                    cnt += 1
                if n == 1:
                    mem[m] = cnt
                    return cnt 
                mem[m] = 1 + cnt + min(helper(n+1, mem), helper(n-1, mem))
                return mem[m]
            mem = {1: 0}
            return helper(n, mem)
    

Log in to reply
 

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