There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:
2, or1 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 <= startValue, target <= 109Instead of moving from the startValue to target, consider reversing the operations. Start from the target and attempt to reach the startValue. If the target is even, divide it by 2. If it is odd, add 1 to it. Continue until the target is less than or equal to the startValue. This allows you to efficiently compute the minimum steps by potentially making large reductions through division by 2.
This C program uses a loop to apply reverse operations to reduce the target to a value no larger than the startValue. If target is even, it is divided by 2; if odd, it is incremented by 1. Lastly, the remaining difference between startValue and target is added to the operations, as this represents the needed decrements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n), where n is the target due to halving operation.
Space Complexity: O(1) as no extra space is used.
Using a greedy approach, always attempt the operation that brings the target closer to the startValue significantly, which is multiplication by 2 in the reverse. Only when all doubling possibilities are exhausted, should we use subtraction/addition operations.
This C solution looks at the current relation between target and startValue, opting to expedite reduction using division when possible, and slow down with addition or subtraction when necessary.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n) due to division operations.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Reverse Operations Approach | Time Complexity: |
| Greedy Approach | Time Complexity: |
Bro Destroyed Leetcode 💀 then got kicked out 😭 • Sajjaad Khader • 24,375 views views
Watch 9 more video solutions →Practice Broken Calculator with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor