[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 \(\textit{startValue} \gt \textit{target}\), so return \(\textit{startValue} \gt \textit{target}\);
  2. Considering such cases: \(2 \to 3\), \(2 \to 5\), \(1 \to 128\), \(1 \to 100\);
  3. \(\textit{startValue} = \textit{startValue} \times 2^i\), when \(\textit{startValue}\) grows bigger, the last \(\textit{startValue}\) is closer to \(\textit{target} / 2\) that we only need double \(\textit{startValue}\) once.

So think reversly:

  1. if target is even, the minimum operand is convert \(startValue\) equal to \(\textit{target} / 2 + 1\);
  2. if target is odd, the minimum operand is convert \(startValue\) equal to \((\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)\).
  • Space Complexity: \(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. 😉😃💗