LeetCode 991. Broken Calculator

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2019/02/12/LeetCode-991-Broken-Calculator/

访问原文「LeetCode 991. Broken Calculator」

题目要求

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

题意解析

目前有一个坏了的计算器，只能有两个操作，一个是加倍也就是乘以2，另外一个是减一。
现在两个数字，X和Y，在使用这个坏计算器的基础上，从X得到Y的最少操作次数。

解法分析

反过来考虑这个问题，也就是如何从Y得到X，而操作变为：

1. 如果Y是偶数，Y = Y / 2
2. 如果Y是奇数，Y = Y + 1

当Y <= X时，无法进行Y = Y / 2，只需要进行Y = Y + 1；
当Y > X时，需要持续的减少Y，直到Y <= X。

• 如果Y是偶数，Y = Y / 2
• 如果Y是奇数，Y = Y + 1
  因为(Y + 1 + 1) / 2 = (Y / 2) + 1，而等号左边需要3步而右边仅需要2步，所以当Y为偶数时仅需要考虑Y = Y / 2。

时间复杂度为O(log(Y));
空间复杂度为O(1)。

解题代码

public int brokenCalc(int X, int Y) {
        int step = 0;
        while (Y > X) {
            Y = Y % 2 > 0 ? Y + 1 : Y / 2;
            step++;
        }
        return step + X - Y;
    }