Ninjas's Robot

Hard
0/120
Average time to solve is 30m
profile
Contributed by
8 upvotes
Asked in companies
AppleLimeroad.comGoogle inc

Problem statement

Ninja has a robot that can move in an infinite number line. The robot starts at position 0, with speed = +1. The robot moves automatically according to the sequence of instructions “A” (Accelerate) and “R” (Reverse).

When robot get an instruction "A", the robot does the following: position += speed, speed *= 2.

When the robot gets an instruction “R”, the robot does the following: if its speed is positive then speed = -1, otherwise speed = +1. The position of the robot will remain the same.

For example, after commands "AAARA", the robot goes to positions 0->1->3->7->7->6, and robot speed goes to 1->2->4->8->-1->-2.

You are given a positive integer ‘TARGET’, and your task is to find and return the length of the shortest sequence of instruction to reach position equals ‘TARGET’.

Note :

The position of the robot can be negative.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. The 'T' test cases follow.

The first line of each test case will contain a single integer ‘TARGET’.

Output Format :

For each test case, print an integer representing the length of the shortest sequence of instruction to reach position equals ‘TARGET’.

Output for every test case will be printed in a separate line.

Note :

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 50
1 <= ‘TARGET’ <= 10000

Time limit: 1 sec

Sample Input 1 :

2
1
2

Sample Output 1 :

1
4
Explanation of sample input 1 :
In the first test case, The shortest sequence of instruction is ‘A’.

In the second test case,  The shortest sequence of instruction is ‘AARA’, and the position changes as 0->1->3->3->2.

Sample Input 2 :

2
6
7

Sample Output 2 :

5
3
Hint

Track all the possible positions of the robot after each instruction.

Approaches (2)
Breadth-First Search

The basic idea is to use modified Breadth-First Search (BFS) here.  We can keep track of all the possible positions of the robot after ‘N’ instructions (N = 0, 1, 2, 3, 4, ...) and return the smallest ‘N’ such that the ‘TARGET’ position is reached

 

The steps are as follows:

  1. Initialize an integer variable ‘N’:= 0.
  2. Create a queue of list/array ‘STATE’  Each element in the queue has an array/list consisting of two elements i.e position and speed. We enqueue list/array [0, 1] in it.
  3. Run a loop till the queue ‘STATE’ is not empty and in each step do the following -:
    1. Let ‘M’ be the size of the queue ‘STATE’
    2. Run a loop where ‘i’ ranges from 0 to ‘M’ and do the following -:
      1. Let ‘POS’ be the 0th element of list/array at front of queue ‘STATE’ and  ‘SPEED’ be its 1st element.
      2. If ‘POS’ = ‘TARGET’ then return ‘N’.
      3. Dequeue the front element of queue ‘STATE’.
      4. Enqueue list/array [‘POS’+’SPEED’, 2*SPEED] and [‘POS’, -1 * SPEED/|SPEED|] where |X| is absolute value of ‘X’
    3. Increment ‘N’ by 1
Time Complexity

O(2^N), where 'N' is the maximum number of instructions.

 

In each step we have two choices ‘R’ or ‘A’, Thus overall there are 2^N choices for ‘N’ instructions. Thus overall complexity will be O(2^N),

Space Complexity

O(2^N), where 'N' is the maximum number of instructions.

 

The space used by the queue will be O(2^N).

Code Solution
(100% EXP penalty)
Ninjas's Robot
Full screen
Console