hardDynamic Programming 1DPure DSA~40 min
Fewest Commands to Reach a Position
A simulated car starts at position 0 with speed +1. Command 'A' accelerates (position += speed; speed *= 2); command 'R' reverses (speed becomes -1 or +1, position unchanged). Find the shortest command string to land exactly on a target.
Problem
Starting at position 0 with speed 1, you issue a sequence of instructions. 'A' sets position += speed then speed *= 2. 'R' sets speed = -1 if it was positive, else 1 (position unchanged). Return the length of the shortest instruction sequence that ends with position exactly equal to target.
Input
A positive integer target.
Output
An integer: the minimum number of instructions.
Constraints
- 1 <= target <= 10000
Examples
Example 1
Input
target = 3
Output
2
'AA' moves 0 -> 1 -> 3.
Example 2
Input
target = 6
Output
5
'AAARA' reaches 6 in 5 instructions.