Watch 10 video solutions for Broken Calculator, a medium level problem involving Math, Greedy. This walkthrough by codestorywithMIK has 11,272 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: You start with a number startValue on a calculator. Two operations are allowed: multiply the number by 2 or subtract 1. The task is to reach target using the minimum number of operations. Brute force simulation grows quickly, so the trick is to reason about the operations mathematically instead of exploring every path.
Approach 1: Reverse Operations Approach (O(log target) time, O(1) space)
The key insight is that working backward from target to startValue is far more efficient than building forward. Instead of asking "how do we reach target from startValue?", ask "what value could produce target in one step?" If target is even, the previous state could only be target / 2 (reverse of multiply by 2). If target is odd, the previous step must have been target + 1 (reverse of subtract 1). You repeatedly apply these reverse operations until target becomes less than or equal to startValue. At that point, the only remaining option is subtracting 1 repeatedly, which takes startValue - target operations. Because each division by 2 halves the number, the loop runs roughly O(log target) times. This method relies on simple arithmetic reasoning from math and eliminates unnecessary exploration.
Approach 2: Greedy Approach (O(log target) time, O(1) space)
This problem naturally fits a greedy strategy. The greedy decision is based on making the move that reduces the distance to the target fastest. When working from the target side, dividing by 2 is always the most powerful reduction when the number is even. If the number is odd, division is impossible, so you increment it first to make it even and enable the divide operation in the next step. Each decision locally minimizes the remaining gap between the current value and startValue. Once the target drops below the starting value, greedy logic no longer applies and the only optimal sequence is subtracting 1 repeatedly. This approach is essentially the reasoning layer behind the reverse-operations solution and explains why those specific transformations produce the optimal path.
Recommended for interviews: Interviewers expect the reverse greedy strategy. A naive forward simulation quickly becomes exponential because doubling overshoots the target and creates many possibilities. Demonstrating the reverse thinking shows strong problem-solving ability and comfort with greedy reasoning and mathematical transformations. The final solution runs in O(log target) time with constant space, which is optimal for this problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Operations Approach | O(log target) | O(1) | Best general solution. Efficiently reduces the target using reverse operations. |
| Greedy Approach | O(log target) | O(1) | Useful for reasoning about why dividing when even and incrementing when odd gives the optimal path. |