[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
- If \(\textit{startValue} \gt \textit{target}\), so return \(\textit{startValue} \gt \textit{target}\);
- Considering such cases: \(2 \to 3\), \(2 \to 5\), \(1 \to 128\), \(1 \to 100\);
- \(\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:
- if target is even, the minimum operand is convert \(startValue\) equal to \(\textit{target} / 2 + 1\);
- if target is odd, the minimum operand is convert \(startValue\) equal to \((\textit{target} + 1) / 2 + 2\).
Let’s coding.
1 | public int brokenCalc(int startValue, int 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. 😉😃💗