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

• 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

``````

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