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