991

991. Broken Calculator (Medium)

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

• multiply the number on display by 2, or
• subtract 1 from the number on display.

Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

 

Example 1:

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

Example 2:

Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

 

Constraints:

• 1 <= x, y <= 109

Companies:
Bloomberg, Arcesium, Nutanix

Related Topics:
Math, Greedy

Similar Questions:

• 2 Keys Keyboard (Medium)

Solution 1. Greedy

Since we are looking for the shortest path, BFS is the first option. But this will create too many states.

We can get the following intuition if we think in the reverse order, get X from Y by dividing by 2 or adding 1.

Intuition:

• If Y < X, we can only keep adding 1s, so it takes X - Y steps.
• If Y > X, we have the two options but we can greedily pick one. It's deterministic.
  • If Y is even, dividing by 2 first is always better than adding 1 first.
    For example, to reach target / 2 + 1, one division and one addition is better than 2 additions and one division.
    After trying more examples, we can see that doing division first then addition is always better than doing addition first than division.
  • If Y is odd, we can only add 1.

// OJ: https://leetcode.com/problems/broken-calculator/
// Author: github.com/lzl124631x
// Time: O(logY)
// Space: O(1)
class Solution {
public:
    int brokenCalc(int X, int Y) {
        int ans = 0;
        while (Y > X) {
            ++ans;
            if (Y % 2) ++Y;
            else Y /= 2;
        }
        return ans + X - Y;
    }
};