Last Updated: 23 Apr, 2021

Ninjas's Robot

Hard

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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:

Initialize an integer variable ‘N’:= 0.
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.
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

Solve now

02 Approach

Let ‘N’ be the number of bits in the binary representation of ‘TARGET’, Then if ‘TARGET’ = 2^N -1, then the shortest sequence will consist of ‘N’ “A”s,

Otherwise, there are two possible ways to reach the target -:

1. To pass out the target and then reverse direction -: Robot first follow the sequence of ‘N’ “A”s and then one ‘R’ to reverse direction, after that, we need to find the shortest sequence length required to reach 2^N-1-’TARGET’, Let ‘M’ be this length, then answer will be N + 1 + M.

2. To go as far as possible before pass ‘TARGET’ then reverse back and again start to move in direction of ‘TARGET’ -: We give robot ‘N-1’ instruction of ‘A’ than one ‘R’ then some ‘K’ instruction of ‘A’ such that K < N.

The steps are as follows:

Create an array/list DP of size 2*TARGET and fill it with 0.
Then we make the recursive function findShortestLenHelper(‘T’) that finds the length of the shortest sequence of instructions to reach position ‘T’. In each recursive step do the following-:
1. If DP[T] > 0, return DP[T].
Let ‘N’ be the number of bits in the binary representation of ‘T’.
If 2^N-1 = T, the Do DP[T] = N.
Otherwise, do DP[T] = findShortestLenHelper(‘T’) (2^N-1-T) + N + 1.
Run a loop where ‘i’ ranges from 0 to N-1 and for each ‘i’ do the following -:
1. DP[T] = min(DP[T], findShortestLenHelper(‘T’ - 2^(N-1)) + 2^i) + N + i + 1);
Return DP[T].
Return findShortestLenHelper(‘TARGET’).

Solve now