Ninjas's Robot
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

Question

Ninjas's Robot

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

Accepted Answer

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:

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

Space Complexity: O(2^n)Explanation:

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

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

Time Complexity: O(2^n)Explanation:

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),

Accepted Answer

Dynamic Programming

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’).

Space Complexity: O(n)Explanation:

O(TARGET), where 'TARGET' is the given integer.

Space used by the ‘DP’ array/list will be O(‘TARGET’).

Time Complexity: O(logn)Explanation:

O(TARGET * log(TARGET)), where 'TARGET' is the given integer.

There is an O(TARGET) state in the DP table and each takes O(log(TARGET)) to compute. Thus overall complexity will be O(TARGET * log(TARGET)),

C++ (g++ 5.4)

/*

    Time Complexity : O(TARGET * log(TARGET)),

    Space Complexity : O(TARGET)



    Where 'TARGET' is the given integer.

*/



#include 

#include 



int findShortestLenHelper(int t, vector &dp){

    //  If state is already computed.

    if (dp[t] > 0)

    {

        return dp[t];

    }



    //  Number of bits.

    int n = floor(log2(t)) + 1;



    if (1 << n == t + 1)

    {

        //  Base case.

        dp[t] = n;

    }

    else

    {

        dp[t] = findShortestLenHelper((1 << n) - 1 - t, dp) + n + 1;

        for (int i = 0; i < n - 1; i++)

        {

            dp[t] = min(dp[t], findShortestLenHelper(t - (1 << (n - 1)) + (1 << i), dp) + n + i + 1);

        }

    }

    return dp[t];

}



int findShortestLen(int target){

    vector dp(2 * target);



    //  Recursively find answer.

    return findShortestLenHelper(target, dp);

}

Python (3.5)

"""

    Time Complexity : O(TARGET * log(TARGET)),

    Space Complexity : O(TARGET)



    Where 'TARGET' is the given integer.

"""

import math



def findShortestLenHelper(t, dp):

    #  If state is already computed.

    if (dp[t] > 0):

        return dp[t]

    



    #  Number of bits.

    n = math.floor(math.log2(t)) + 1



    if (1 << n == t + 1):

        #  Base case.

        dp[t] = n

    

    else:

        dp[t] = findShortestLenHelper((1 << n) - 1 - t, dp) + n + 1

        for i in range(n-1):

            dp[t] = min(dp[t], findShortestLenHelper(t - (1 << (n - 1)) + (1 << i), dp) + n + i + 1)

          

    return dp[t]





def findShortestLen(target):

    dp = [0]*(2*target)



    #  Recursively find answer.

    return findShortestLenHelper(target, dp)

Java (SE 1.8)

/*

    Time Complexity : O(TARGET * log(TARGET)),

    Space Complexity : O(TARGET)



    Where 'TARGET' is the given integer.

*/



import java.util.ArrayList;



public class Solution 

{

    public static int findShortestLenHelper(int t, ArrayList dp)

    {

        //  If state is already computed.

        if (dp.get(t) > 0)

        {

            return dp.get(t);

        }

    

        //  Number of bits.

        int n = ((int)(Math.log(t) / Math.log(2))) + 1;

    

        if ((1 << n) == t + 1)

        {

            //  Base case.

            dp.set(t ,  n);

        }

        else

        {

            dp.set(t , findShortestLenHelper((1 << n) - 1 - t, dp) + n + 1);

            for (int i = 0; i < n - 1; i++)

            {

                dp.set(t , Math.min(dp.get(t), findShortestLenHelper(t - (1 << (n - 1)) + (1 << i), dp) + n + i + 1));

            }

        }

        return dp.get(t);

    }



    public static int findShortestLen(int target) 

    {

        ArrayList dp = new ArrayList<>(2 * target);

        for(int i=0 ; i<2*target ; i++)

        {

            dp.add(0);

        }



        //  Recursively find answer.

        return findShortestLenHelper(target, dp);

    }

}

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 :

Input Format :

Output Format :

Note :

Constraints :

Top LimeRoad Full Stack Developer interview questions & answers

Popular interview questions of Full Stack Developer