Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.) Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction "A", your car does the following: position += speed, speed *= 2.
When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)
For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1. Now for some target position, return the length of the shortest sequence of instructions to get there.
Constraints:- 1<=target<=10^4
1) Input:- 3 Output:- 2 (shortest instruction is AA)
2) Input:- 6 Output:- 5 (AAARA)
3) Input:-5 Output:-7
Can someone please help me with this problem?
Thanks.
The key observation is that we don’t want to go very far and don’t want to speed very much. You should think about limits on those two values and then you can run simple bfs where the state is (position, current speed). Also maybe greedy or dp approach is possible — I’ll think about it.
Yea. I don't know how to find the limits appropriately. I got TLE because of naively running BFS on (position,speed).
Can someone please help?