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 <= 109The key to solving #991 Broken Calculator is realizing that working backwards from the target is more efficient than building forward from the start value. The calculator allows two operations: *2 and -1. If we simulate forward, the search space grows quickly.
Instead, apply a greedy strategy by reducing the target toward startValue. If the target is greater than the start value, check whether it is even or odd. When the target is even, it likely came from a doubling operation, so dividing by 2 reverses that step. When the target is odd, incrementing it makes it even so it can be halved in the next step. This minimizes unnecessary operations.
Once the target becomes less than or equal to the start value, the remaining difference can be handled with simple decrement operations. This greedy reverse simulation keeps the solution efficient with a logarithmic number of steps.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Reverse Simulation | O(log target) | O(1) |
Sajjaad Khader
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.
Time Complexity: O(log n), where n is the target due to halving operation.
Space Complexity: O(1) as no extra space is used.
1#include <stdio.h>
2
3int brokenCalc(int startValue, int target) {
4 int operations = 0;
5 while (
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.
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.
Time Complexity: O(log n) due to division operations.
Space Complexity: O(1).
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems similar to Broken Calculator appear in FAANG-style interviews because they test greedy thinking and reverse problem-solving strategies. It evaluates a candidate's ability to recognize optimal transformations.
The optimal approach uses a greedy reverse strategy. Instead of transforming startValue to target, you work backward from the target by dividing by 2 when even or incrementing when odd until it reaches the start value.
Forward simulation can lead to many unnecessary operations and a larger search space. By reversing the process, you always make the most impactful move—halving when possible—resulting in a logarithmic number of steps.
No special data structure is needed. The solution relies on simple arithmetic operations and a loop to repeatedly adjust the target value until it matches the start value.
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.