991. Broken Calculator

Problem

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

Problem Summary

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

• Double: Multiply the number on the display by 2;
• 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.

Solution Ideas

• Seeing that the data scale of this problem is very large, 10^9, the algorithm can only use O(sqrt(n)), O(log n), or O(1). O(sqrt(n)) and O(1) are impossible for this problem. So, estimating from the data scale, this problem can only try an O(log n) algorithm. An O(log n) algorithm includes binary search, but this problem does not quite fit the background of a binary search algorithm. Multiplication by 2 clearly appears in the problem, which is obviously something that can achieve O(log n). The final solution idea is determined to be a mathematical method, using multiplication by 2 or division by 2 in the loop.
• Since the operations of multiplying by 2 and subtracting one appear, it is easy to consider parity. The problem asks for the minimum number of operations. With a greedy idea, we should use the division by 2 operation as much as possible so that Y and X become close in size, and finally use the add-one operation for fine-tuning. As long as Y is greater than X, perform the division operation. Of course, parity needs to be considered here: if Y is odd, first add one to make it even and then divide by two; if Y is even, divide by two directly. Continue this operation until Y is not greater than X, and finally perform X-Y addition operations for fine-tuning.

Code

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
}