By Long Luo
This article is the solution Greedy: Reverse Thinking with Binary Algorithm of Problem 991. Broken Calculator.
Intuition
- If startValue>target, so return startValue>target;
- Considering such cases: 2→3, 2→5, 1→128, 1→100;
- startValue=startValue×2i, when startValue grows bigger, the last startValue is closer to target/2 that we only need double startValue once.
So think reversly:
- if target is even, the minimum operand is convert startValue equal to target/2+1;
- if target is odd, the minimum operand is convert startValue equal to (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. 😉😃💗