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.
Instead 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.
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.
Time Complexity: O(log n) due to division operations.
Space Complexity: O(1).
We can use a reverse calculation method, starting from target. If target is odd, then target = target + 1, otherwise target = target / 2. We accumulate the number of operations until target leq startValue. The final result is the number of operations plus startValue - target.
The time complexity is O(log n), where n is target. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Reverse Operations Approach | Time Complexity: |
| Greedy Approach | Time Complexity: |
| Reverse Calculation | — |
| 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. |
Broken Calculator | Greedy | Samsung | Leetcode 991 • codestorywithMIK • 11,272 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