[Leetcode][991. Broken Calculator] Greedy: Reverse Thinking with Binary Algorithm

By Long Luo

This article is the solution of Problem 991. Broken Calculator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 <= 10^9

Greedy

  1. If startValue>target\textit{startValue} > \textit{target}, so return startValue>target\textit{startValue} > \textit{target};
  2. Considering such cases: 2 -> 3, 2 -> 5, 1 -> 128, 1 -> 100;
  3. startValue=startValue×2i\textit{startValue} = \textit{startValue} \times 2^i, when startValue\textit{startValue} grows bigger, the last startValue\textit{startValue} is closer to target/2\textit{target} / 2 that we only need double startValue\textit{startValue} once.

So think reversly:

  1. if target is even, the minimum operand is convert startValuestartValue equal to target/2+1target / 2 + 1;
  2. if target is odd, the minimum operand is convert startValuestartValue equal to (target+1)/2+2(target + 1) / 2 + 2.

Let’s coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int brokenCalc(int startValue, int target) {
if (startValue >= target) {
return startValue - target;
}

int ans = 0;
while (startValue < target) {
if (target % 2 == 0) {
target >>= 1;
ans++;
} else {
target = (target + 1) >> 1;
ans += 2;
}
}

return ans + startValue - target;
}

Analysis

  • Time Complexity: O(logn)O(\log n).
  • Space Complexity: O(1)O(1).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗