586. Broken Keypad Calculator
A pocket calculator in a repair shop has only two working keys. Its display currently shows the integer start. Pressing the DOUBLE key multiplies the displayed number by 2, and pressing the MINUS key subtracts 1 from it. Every other key is dead, so these are the only moves, and the display may hold any integer value while you work.
The technician wants the display to show exactly target. Return the smallest number of key presses that turns start into target. If start already equals target, no presses are needed. A solution that works backwards from target runs in O(log target) time and O(1) space.
Example 1
- Input:
- start = 3, target = 10
- Output:
- 3
- Explanation:
Double 3 to get 6, subtract one to get 5, and double to get 10, which takes three presses.
Example 2
- Input:
- start = 9, target = 4
- Output:
- 5
- Explanation:
Doubling only makes the number larger, so the only choice is to press MINUS five times.
Example 3
- Input:
- start = 2, target = 15
- Output:
- 4
- Explanation:
Double 2 three times to reach 16, then press MINUS once to reach 15, for four presses.
Constraints
- 1 ≤ start ≤ 109
- 1 ≤ target ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log target)
- Space
- O(1)