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

By Long Luo

This article is the solution Greedy: Reverse Thinking with Binary Algorithm of Problem 991. Broken Calculator.

Intuition

  1. If startValue>target\textit{startValue} \gt \textit{target}, so return startValue>target\textit{startValue} \gt \textit{target};
  2. Considering such cases: 232 \to 3, 252 \to 5, 11281 \to 128, 11001 \to 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+1\textit{target} / 2 + 1;
  2. if target is odd, the minimum operand is convert startValuestartValue equal to (target+1)/2+2(\textit{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(logn).
  • 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. 😉😃💗