Broken Dial Calculator
MediumGreedy
Problem
An old calculator shows the number start. Only two buttons still work: double (multiply the display by 2) and minus one (subtract 1).
Return the minimum number of button presses needed to make the display show target.
Example 1
- Input:
- start = 3, target = 10
- Output:
- 3
3 → 6 (double) → 5 (minus one) → 10 (double).
Example 2
- Input:
- start = 5, target = 8
- Output:
- 2
5 → 4 → 8.
Example 3
- Input:
- start = 9, target = 4
- Output:
- 5
Only minus one helps: five presses.
Constraints
- 1 ≤ start, target ≤ 10^9
Hint
Show the first hint
Going forward, it is unclear when to double and when to subtract. What if you start from the target instead?
Walkthrough
How to approach it
01Clarify before coding
- Can the display go to 0 or negative? It could, but it never helps: we only need positive values.
- Is target allowed to be smaller than start? Yes; then only subtractions are useful.
- Are the values large? Up to 10^9, so BFS over values is too slow and too memory-hungry.
02Brute force
BFS over display values from start, with edges ×2 and −1, until target is found.
Cost: Visits up to O(target) states, around 10^9: too slow and too much memory.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.