465. Follow Instructions
0
Hard
Sumit is driving his car on an infinite number line. The car starts at position 0 and has a speed of +1. The car can move in both positive and negative directions. Sumit can control the car by giving it a sequence of instructions, which can be either 'A' (accelerate) or 'R' (reverse):
For 'A' : Accelerate
Actions Taken :
-> position += speed
-> speed *=2 For 'R'
Actions Taken :
If speed > 0, then speed = -1,
Otherwise, speed = 1. The position of the car remains the same when 'R' is executed. Given a target position, you need to determine the length of the shortest sequence of instructions required to reach that target.
For 'A' : Accelerate
Actions Taken :
-> position += speed
-> speed *=2 For 'R'
Actions Taken :
If speed > 0, then speed = -1,
Otherwise, speed = 1. The position of the car remains the same when 'R' is executed. Given a target position, you need to determine the length of the shortest sequence of instructions required to reach that target.
Input Format
The target position as an integer.
Output Format
The length of the shortest sequence of instructions required to reach the target position.
Example
Input
6
Output
5
Constraints
1 <= target <= 10^4
Loading...
View Submissions
Console