題目

On a broken calculator that has a number showing on its display, we can perform two operations:

• Double: Multiply the number on the display by 2, or;
• Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

1. 1 <= X <= 10^9
2. 1 <= Y <= 10^9

題目大意

在顯示着數字的壞計算器上，我們可以執行以下兩種操作：

• 雙倍（Double）：將顯示屏上的數字乘 2；
• 遞減（Decrement）：將顯示屏上的數字減 1 。

最初，計算器顯示數字 X。返回顯示數字 Y 所需的最小操作數。

解題思路

• 看到本題的數據規模非常大，10^9，算法只能採用 O(sqrt(n))、O(log n)、O(1) 的算法。O(sqrt(n)) 和 O(1) 在本題中是不可能的。所以按照數據規模來估計，本題只能嘗試 O(log n) 的算法。O(log n) 的算法有二分搜索，不過本題不太符合二分搜索算法背景。題目中明顯出現乘 2，這很明顯是可以達到 O(log n) 的。最終確定解題思路是數學方法，循環中會用到乘 2 或者除 2 的計算。
• 既然出現了乘 2 和減一的操作，很容易考慮到奇偶性上。題目要求最小操作數，貪心思想，應該儘可能多的使用除 2 操作，使得 Y 和 X 大小差不多，最後再利用加一操作微調。只要 Y 比 X 大就執行除法操作。當然這裏要考慮一次奇偶性，如果 Y 是奇數，先加一變成偶數再除二；如果 Y 是偶數，直接除二。如此操作直到 Y 不大於 X，最後執行 X-Y 次加法操作微調即可。

參考代碼

package leetcode

func brokenCalc(X int, Y int) int {
	res := 0
	for Y > X {
		res++
		if Y&1 == 1 {
			Y++
		} else {
			Y /= 2
		}
	}
	return res + X - Y
}