Check if it is possible to return to the starting position after moving in the given directions
Given a string S having N directions in which a person travels. The task is to check if he/she will be able to return to the same place where he/she started. On Day i(1 <= i <= N), he will travel a positive distance in the following direction:
North if the i-th letter of str is N
West if the i-th letter of str is W
South if the i-th letter of str is S
East if the i-th letter of str is E
If he can return back to the place where he starts after nth day, print “YES” else print “NO”.
Examples:
Input: str = “NNNWEWESSS”
Output: YES
On the 1st, 2nd, and 3rd day he goes to north and on the 4th day he goes west, then eventually
returns where he was standing on the 3rd day on the 5th day, then on the 6th day he again goes to
west.On the 7th day he again return exactly to where he was standing on the 5th day.And on the
10th day he returns home safely.
Input: str = “NW”
Output: NO
Approach: There has to be a same number of N as there are a number of S and also the same number of E as there is W. So, count each type of directions given and just check if they are equal or not.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include<bits/stdc++.h> using namespace std; int main() { string st = "NNNWEWESSS" ; int len = st.length(); int n = 0 ; // Count of North int s = 0 ; // Count of South int e = 0 ; // Count of East int w = 0 ; // Count of West for ( int i = 0; i < len ; i++ ) { if (st[i]== 'N' ) n += 1; if (st[i] == 'S' ) s += 1; if (st[i] == 'W' ) w+= 1 ; if (st[i] == 'E' ) e+= 1 ; } if (n == s && w == e) cout<<( "YES" )<<endl; else cout<<( "NO" )<<endl; } // This code is contributed by // Sahil_Shelangia |
Java
// Java implementation of above approach public class GFG { public static void main(String args[]) { String st = "NNNWEWESSS" ; int len = st.length(); int n = 0 ; // Count of North int s = 0 ; // Count of South int e = 0 ; // Count of East int w = 0 ; // Count of West for ( int i = 0 ; i < len ; i++ ) { if (st.charAt(i)== 'N' ) n+= 1 ; if (st.charAt(i) == 'S' ) s+= 1 ; if (st.charAt(i) == 'W' ) w+= 1 ; if (st.charAt(i) == 'E' ) e+= 1 ; } if (n == s && w == e) System.out.println( "YES" ); else System.out.println( "NO" ) ; } // This Code is contributed by ANKITRAI1 } |
Python
# Python implementation of above approach st = "NNNWEWESSS" length = len (st) n = 0 # Count of North s = 0 # Count of South e = 0 # Count of East w = 0 # Count of West for i in range (length): if (st[i] = = "N" ): n + = 1 if (st[i] = = "S" ): s + = 1 if (st[i] = = "W" ): w + = 1 if (st[i] = = "E" ): e + = 1 if (n = = s and w = = e): print ( "YES" ) else : print ( "NO" ) |
C#
// C# implementation of above approach using System; class GFG { // Main Method public static void Main() { string st = "NNNWEWESSS" ; int len = st.Length; int n = 0 ; // Count of North int s = 0 ; // Count of South int e = 0 ; // Count of East int w = 0 ; // Count of West for ( int i = 0; i < len ; i++ ) { if (st[i]== 'N' ) n += 1 ; if (st[i] == 'S' ) s += 1 ; if (st[i] == 'W' ) w += 1 ; if (st[i] == 'E' ) e += 1 ; } if (n == s && w == e) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ) ; } } // This code is contributed by Subhadeep |
Javascript
<script> // JavaScript implementation of the approach // driver code let st = "NNNWEWESSS" ; let len = st.length; let n = 0 ; // Count of North let s = 0 ; // Count of South let e = 0 ; // Count of East let w = 0 ; // Count of West for (let i = 0; i < len ; i++ ) { if (st[i]== 'N' ) n += 1 ; if (st[i] == 'S' ) s += 1 ; if (st[i] == 'W' ) w += 1 ; if (st[i] == 'E' ) e += 1 ; } if (n == s && w == e) document.write( "YES" ); else document.write( "NO" ) ; </script> |
PHP
<?php // PHP implementation of above approach $st = "NNNWEWESSS" ; $len = strlen ( $st ); $n = 0; // Count of North $s = 0; // Count of South $e = 0; // Count of East $w = 0; // Count of West for ( $i = 0; $i < $len ; $i ++ ) { if ( $st [ $i ] == 'N' ) $n += 1; if ( $st [ $i ] == 'S' ) $s += 1; if ( $st [ $i ] == 'W' ) $w += 1 ; if ( $st [ $i ] == 'E' ) $e += 1; } if ( $n == $s && $w == $e ) echo "YES\n" ; else echo "NO\n" ; // This code is contributed by // Rajput-Ji ?> |
YES
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1) as constant space is used.
Approach 2:
- The program initializes a string variable moves with a sequence of characters representing moves (north, south, east, west).
- It initializes two integer variables x and y to 0, which represent the current position of the person.
- The program then iterates through each character in the moves string using a range-based for loop.
- Inside the loop, the program checks the value of each character and increments or decrements x or y accordingly.
- If the final value of x and y are both 0, the program prints “YES” to indicate that the person has returned to the starting point, otherwise it prints “NO”.
- Finally, the program returns 0 to indicate successful completion.
Here is the code of above approach:
C++
#include <bits/stdc++.h> using namespace std; int main() { string moves = "NNNWEWESSS" ; int x = 0, y = 0; for ( char move : moves) { if (move == 'N' ) y++; else if (move == 'S' ) y--; else if (move == 'E' ) x++; else if (move == 'W' ) x--; } if (x == 0 && y == 0) cout << "YES" << endl; else cout << "NO" << endl; return 0; } |
Java
import java.util.*; public class GFG { public static void main(String[] args) { String moves = "NNNWEWESSS" ; int x = 0 , y = 0 ; // Loop through each move and update the player's position for ( char move : moves.toCharArray()) { if (move == 'N' ) { y++; } else if (move == 'S' ) { y--; } else if (move == 'E' ) { x++; } else if (move == 'W' ) { x--; } } // Check if the player has returned to the starting position if (x == 0 && y == 0 ) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } |
Python3
# Declare and initialize variables moves = "NNNWEWESSS" x = 0 y = 0 # Loop through each move and update the player's position for move in moves: if move = = 'N' : y + = 1 elif move = = 'S' : y - = 1 elif move = = 'E' : x + = 1 elif move = = 'W' : x - = 1 # Check if the player has returned to the starting position if x = = 0 and y = = 0 : print ( "YES" ) else : print ( "NO" ) |
C#
using System; class Program { static void Main( string [] args) { string moves = "NNNWEWESSS" ; int x = 0, y = 0; foreach ( char move in moves) { // Check the direction of the current move if (move == 'N' ) y++; else if (move == 'S' ) y--; else if (move == 'E' ) x++; else if (move == 'W' ) x--; } // Check if the final position is the starting point // (0, 0) if (x == 0 && y == 0) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } |
Javascript
// Declare and initialize variables let moves = "NNNWEWESSS" ; let x = 0, y = 0; // Loop through each move and update the player's position for (let move of moves) { if (move == 'N ') y++; else if (move == ' S ') y--; else if (move == ' E ') x++; else if (move == ' W') x--; } // Check if the player has returned to the starting position if (x == 0 && y == 0) { console.log( "YES" ); } else { console.log( "NO" ); } |
Output:
YES
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1) as constant space is used.