Broken Calculator
Medium · Greedy · Math · Greedy
Problem
A broken calculator shows the integer startValue. Only two keys still work:
- double: multiply the displayed number by 2,
- decrement: subtract 1 from the displayed number.
Return the minimum number of key presses needed to display target.
Examples
Input: startValue = 3, target = 10 Output: 3
3 → 6 → 5 → 10: double, decrement, double.
Input: startValue = 5, target = 8 Output: 2
5 → 4 → 8: decrement, then double.
Input: startValue = 9, target = 4 Output: 5
Doubling only moves away, so decrement five times.
Constraints
- 1 <= startValue, target <= 10^9
Approaches
- Baseline: breadth-first search over displayed numbers — time O(target), space O(target)
Follow-up
What if the calculator could also add 1? Then the reverse moves are halve, add 1 and subtract 1, and the simple parity rule needs one more look ahead: see the use case "Fewest steps down to 1". And if the number of doublings is limited, the same backward greedy spends the doublings where they save the most (the other use case).
Related problems
Start free on Cariara · Coding problems · System design studio
