leetcode 991

问题

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:

1
2
3
Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

1
2
3
Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

1
2
3
Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

1
2
3
Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

  1. 1 <= X <= 10^9
  2. 1 <= Y <= 10^9

分析

我们可以从Y到X进行逆向考虑，那么现在允许的操作就变成了两个，一个操作是除2操作，另一个操作是加1操作。当Y小于X的时候，要是Y变成X，那么只能进行加1操作，否则就会使Y与X之间的差距越来越大。

那么当Y大于X时，若Y是偶数，那么Y最好进行的操作就是除2操作，如果Y是奇数那么Y能够进行的操作就只有加1操作。

证明：因为Y比X要大，那么从Y向X变化的过程中一定存在除2这个操作。那么我们假设Y现在是一个偶数，要想进行除2这个操作，Y一定要先变化为一个偶数（或者不进行变化），假设Y增加了2N，然后除以2得到了Z。这个过程中执行的步骤为（2N+1），若我们先执行除2操作的话，从Y（偶数）变化到Z所需要的步骤就是（N+1），显然当，Y为偶数的时候，选择进行除2操作是最优的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
// 迭代解法
class Solution {
public:
    int brokenCalc(int X, int Y) {
        int ans = 0;
        while (X < Y) {
            Y = (Y%2) == 1? Y+1: Y/2;
            ans++;
        }
        return ans + (X-Y);
    }
};

递归解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 递归解法
class Solution {
public:
    int brokenCalc(int X, int Y) {
        if (X >= Y)
            return X-Y;
        if (Y%2) {
            return 1 + brokenCalc(X, Y+1);
        } else {
            return 1 + brokenCalc(X, Y/2);
        }
    }
};