Circular Move

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
American ExpressAmazonCerner Corporation

Problem statement

You have a robot currently standing at the origin (0, 0) of a two-dimensional grid and facing north direction. You are given a sequence of moves for the robot in the form of a string of size 'N'. You are required to find whether the path followed by the robot upon taking the moves is circular or not.

A sequence of moves is circular if and only if the robot ends up from where it initially started.

The sequence of moves contains only three types of moves.

'G': it means that the robot will move 1 unit in the direction it is facing.

'L': it means that the robot will move 90 degrees towards its left. For example, if the robot is facing north and it has to make an ‘L’ move, then it will start facing the west direction.

'R': it means the robot will move 90 degrees towards its right. For example, if the robot is facing north and it has to make an ‘R’ move then it will start facing the east direction.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases/queries to be run. 
Then the test cases follow. 

The first and the only line of input for each test case/query contains a string representing the sequence of moves.
Note: 
The sequence of moves will always be:
1. A valid one.

2. In uppercase characters without spaces in between.
Output Format: 
For each test case, print a single line containing ‘True’ if the sequence of moves is circular, print ‘False’ otherwise(without quotes).

The output for every test case will be printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
0 <= N <= 10 ^ 4

All the characters of the string will be ‘L’, ‘R’, and ‘G’.

Time Limit: 1 sec.
Sample Input 1:
1
GRRG
Sample Output 1:
True
Explanation of the Sample Input 1:
There is only 1 test case and for the first test case, the sequence of the moves is ‘GRRG’.

The Robot is standing at (0,0) and its face is toward the north direction now the first move is ‘G’ so it moves one direction towards the north. The new position of the robot is (0,1). Now the next move is ‘R’ so it starts facing towards the east. The next move is again ‘R’ so it starts facing towards the south. The next move is ‘G’ so it moves 1 unit towards the south, therefore, the new position of the robot is (0,0). The start position and the end position of the robot are the same hence the sequence of the moves is circular.
Sample Input 2 :
1
GRG
Sample Output 2 :
False
Explanation of the Sample Input 2:
For the first test case, the Robot is standing at (0,0) and facing the north direction now the first move is ‘G’ so it moves one direction towards the north. The new position of the robot is (0,1). Now the next move is ‘R’ so it starts facing towards the east. The next move is ‘G’ so it moves one direction in the east direction and its new position is (1,1). After all the moves, the robot has not reached the same place from where it started and hence the path is not circular.
Hint

Try to do as asked in the problem and move the robot accordingly.

Approaches (1)
Optimal Approach

Initialize a variable ‘direction’ with 0 which means that the robot is initially facing towards the north.

direction: 0 -> Robot is facing towards the North
direction: 1 -> Robot is facing towards the West 
direction: 2 -> Robot is facing towards the South 
direction: 3 -> Robot is facing towards the West

 

Initialize two variables ‘x’ and ‘y’ as 0. They will represent the position of the robot which is initially (0,0). Now, execute the moves from the sequence one by one and 

  • If the current move is  ‘L’ increase the direction by 1 and if the direction becomes 4 make it 0.
  • If the current move is ‘R’ then decrease the direction by 1 and if it becomes -1 then make it 3.
  • If the current move is ‘G’ then check the direction
    • If the direction is 0 then y = y + 1
    • If the direction is 1 then x = x - 1
    • If the direction is 2 then y = y - 1
    • If the direction is 3 then x = x + 1

Now simply check if the current position is (0,0) or not. If it is (0,0) then this sequence of moves is circular otherwise it is not circular.

Time Complexity

O(N), where ‘N’ is the number of moves in the sequence.
 

We are traversing each move only once.

Space Complexity

O(1).

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Circular Move
Full screen
Console