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 <= X <= 10^9
1 <= Y <= 10^9
Solution: Greedy
Thinking backwards, making Y <= X by adding 1 or dividing 2.
If Y is even, (Y + 1) // 2 == Y // 2, there is no need to do the extra step
If Y is odd (Y + 1) // 2 = (Y // 2) + 1, so only do + 1 when Y is odd
Time complexity: O(log(Y-X))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 |
// Author: Huahua, running time: 4 ms, 4.7 MB class Solution { public: int brokenCalc(int X, int Y) { if (X <= Y) return X - Y; return 1 + brokenCalc(X, Y % 2 ? Y + 1 : Y / 2); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment