题目描述

在一个破损的计算器上可以显示一个数字，我们有两种操作：

• Double：将当前数字乘 2，或，
• Decrement：将当前数字减 1。

一开始，计算器显示数字 X。

返回最少的操作次数，使得显示数字 Y。

样例

输入：X = 2, Y = 3
输出：2
解释：使用 double， 然后 decrement，{2 -> 4 -> 3}.

输入：X = 5, Y = 8
输出：2
解释：使用 decrement 然后 double，{5 -> 4 -> 8}.

输入：X = 3, Y = 10
输出：3
解释：使用 double，decrement 和 double {3 -> 6 -> 5 -> 10}.

输入：X = 1024, Y = 1
输出：1023
解释：使用 1023 次 decrement 操作。

注意

• 1 <= X <= 10^9
• 1 <= Y <= 10^9

算法

(找规律) $O(\log Y)$

1. 逆向操作，当 Y > X 时，如果 Y 为偶数，则 Y /= 2，否则 Y + 1，累计答案 1 次。
2. 如果操作过程中 Y <= X，则终止操作，然后答案累计 X - Y 次。
3. 证明，当 Y 为偶数时，显然让 X 通过一次加倍操作变成 Y 是最好的；当 Y 为奇数时，最好情况也是让 X 加倍后减去 1。
4. 如果 Y 在变化中超过了 X，则说明无论如何 X 需要在第一步就倒退，否则需要更多的代价来倒退。

时间复杂度

• 最多 $O(\log Y)$ 次就能使得 Y <= X，故时间复杂度为 $O(\log Y)$。

空间复杂度

• 只需要常数空间记录答案。

C++ 代码

class Solution {
public:
    int brokenCalc(int X, int Y) {
        int ans = 0;
        while (Y > X) {
            if (Y % 2 == 0)
                Y /= 2;
            else
                Y++;
            ans++;
        }
        return ans + X - Y;
    }
};