LeetCode：991. Broken Calculator

此文为LeetCode 991. Broken Calculator 的题解。

题意

有一台坏掉的计算器，能够显示一个数字，我们可以对这个数字做两个操作：

• 乘 二: 将显示的数字乘以2, 或者;
• 减一 : 将显示的数字减1.

初始时，计算器显示数字 X .

返回要得到数字 Y 需要的最小操作次数。

题解

如果X>Y，则只能执行减一操作。否则，如果Y是奇数，则上一步操作一定是X 减一 ；如果Y是偶数，则上一步操作只能是X 乘二 。

只需要通过上述规则，由Y反推X即可。

代码

/**
 * https://www.robberphex.com/broken-calculator/
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Broken Calculator.
 * Memory Usage: 33 MB, less than 8.71% of Java online submissions for Broken Calculator.
 */
class Solution {
    public int brokenCalc(int X, int Y) {
        int res = 0;
        // 如果X<Y，则只能-1，故直接走return句
        while (X < Y) {
            if (Y % 2 == 1) {
                Y += 1;
            } else {
                Y /= 2;
            }
            res++;
        }
        return res + X - Y;
    }

    public static void main(String[] args) {
        int res = new Solution().brokenCalc(2, 3);
        System.out.println(res);
    }
}