Using Greedy Algorithm to Fix the 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 <= X <= 10^9
1 <= Y <= 10^9

Greedy Algorithm Fixes the Broken Calculator

A greedy algorithm has a strategy that picks the current optimial solution which will lead to a global optimial solution. But it does not work for all types of problems e.g. Dynamic Programming.

For simplicity, we can look into the problem slightly in a different way. We can transform Y to X, thus only two operations are allows: divided number by two (if it is an even number), and add one to the number.

Dividing by two (if it is an even number) is obviously better (shorter) than do minus, minus, divide, plus, plus. If it is odd number, it seems that we can only increment this number by one.

If Y is smaller than X, then, the greedy approach requires (X – Y) steps. The worst case scenario complexity is O(Max(1, X – Y)).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int brokenCalc(int X, int Y) {
        int ans = 0;
        while (X < Y) {
            if (Y % 2 == 0) {
                Y /= 2;
            } else {
                Y ++;
            }
            ans ++;
        }
        return ans + X - Y;
    }
};

class Solution {
public:
    int brokenCalc(int X, int Y) {
        int ans = 0;
        while (X < Y) {
            if (Y % 2 == 0) {
                Y /= 2;
            } else {
                Y ++;
            }
            ans ++;
        }
        return ans + X - Y;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —