Skip to main content

0991 - Broken Calculator (Medium)

https://leetcode.com/problems/broken-calculator/

Problem Statement​

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 <= 10^9

Approach 1: Greedy​

We solve it backwards. For operation 1, instead of multiplying the number by 22, we divide it by 22 if possible. Similarly, we add 11 to the number for operation 2. At the end, the number may be less than startValue, in this case we can only use operation 2.

Written by @wingkwong
class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int ans = 0;
        while (target > startValue) {
            if (target % 2 == 0) {
                // use operation 1
                target /= 2;
            } else {
                // use operation 2
                target += 1;
            }
            // increase number of operations
            ans += 1;
        }
        // target can be less than startValue
        // e.g. right after operation 1
        if (target < startValue) {
            // use operation 2
            ans += startValue - target;
        }
        return ans;
    }
};