Clear Python solution, easy to understand, from the idea of Branch & Bound


  • 0
    A

    The idea is to build a Priority Queue (by using heap) to record all possible moving paths, and update the count of moves (variable ans) for the best moving strategy. Heap records the tuple of (count of moves to arrive here, the current number n). If the count of current moves is larger than our latest ans , then we know this path is not the best path (because it is worse than a existing path with the count of ans), hence we skip it.

    The performance of the following code is not the best. But I think it is easier to explain during an interview. Hope it helps.

    import heapq
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        queue = [(0, n)]
        ans = n
        while queue:
            count, num = heapq.heappop(queue)
            if ans <= count: continue     # bound
            while num % 2 == 0:
                count += 1
                num /= 2
            if num == 1:
                ans = min(count, ans)
            else:
                heapq.heappush(queue, (count+2, (num+1)/2))
                heapq.heappush(queue, (count+2, (num-1)/2))
        return ans
    
    
    

Log in to reply
 

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