Given n integers in a maze indicating a number of moves to be made from that position and a string which has “>” and “<” indicating which side to move. The starting position is the first position.
Print whether it stays inside the array or moves out of the array.
Example:
Input : 3
2 1 1
> > <
Output: It stays inside forever
Explanation:
It moves towards right by a position of 2,
hence is at the last index, then it moves
to the left by 1, and then it again moves
to the right by 1. Hence it doesn't go
out.
Input: 2
1 2
> <
Output: comes out
Explanation:
Starts at 0th index, moves right by 1
position, and then moves left by 2 to
come out
The approach to the above problem is as follows:
We start from the 0th index and move until we exceed n or decrease 0. If we reach the same position twice, then we are in an infinite loop and can never move out.
* use a mark array to mark the visited positions
* start from 0th index and check the sign of move and move to that place, marking that position as visited
* if visited we can never move out, hence break out
* check the reason for the break from loop, and print the desired result.
// below is the python implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether it will stay inside // or come out void checkingPossibility(vector<int>a, int n,string s){ // marks all the positions that is visited vector<int>mark(n,0); // Initial starting point int start = 0; // initial assumption is it comes out int possible = 1; // runs till it is inside or comes out while(start >= 0 && start < n){ // if the movement is towards left // then we move left. The start variable // and mark that position as visited // if not visited previously. Else we // break out if(s[start] == '<'){ if(mark[start] == 0){ mark[start] = 1; start -= a[start]; } // It will be inside forever else{ possible = 0; break; } } // If the movement is towards right, then // we move right. The start variable and // mark that position as visited if not // visited previously else we break out else{ if(mark[start] == 0){ mark[start] = 1; start += a[start]; } // it will be inside forever else{ possible = 0; break; } } } if(possible == 0) cout<<"it stays inside forever"<<endl; else cout<<"comes out"<<endl; } // Driver Code int main(){ int n = 2; string s = "><"; vector<int>a = {1, 2}; checkingPossibility(a, n, s); } // This code is contributed by shinjanpatra |
Java
//Java Possibility of moving out of maze import java.io.*; class GFG { // Function to check whether it // will stay inside or come out static void checkingPossibility( int a[], int n, String s) { // marks all the positions that is visited int mark[] = new int[a[0] * n] ; // Initial starting point int start = 0; // initial assumption is it comes out int possible = 1; //runs till it is inside or comes out while( start >= 0 && start < n) { //if the movement is towards left //then we move left. The start variable // and mark that position as visited // if not visited previously. Else we // break out if (s == "<") { if (mark[start] == 0) { mark[start] = 1; start -= a[start] ; } // It will be inside forever else{ possible = 0; break;} } // If the movement is towards right, then // we move right. The start variable and // mark that position as visited if not // visited previously else we break out else { if (mark[start] == 0) { mark[start] = 1; start += a[start] ; } // it will be inside forever else { possible = 0; break; } } } if (possible == 0) System.out.print( "it stays inside forever"); else System.out.print ("comes out"); } // Driver code public static void main (String[] args) { int n = 2; String s = "><"; int a[] = {1, 2}; checkingPossibility(a, n, s); } } // This code is contributed by vt_m. |
Python3
# Function to check whether it will stay inside # or come out def checkingPossibility(a, n, s): # marks all the positions that is visited mark = [0] * n # Initial starting point start = 0 # initial assumption is it comes out possible = 1 # runs till it is inside or comes out while start >= 0 and start < n: # if the movement is towards left # then we move left. The start variable # and mark that position as visited # if not visited previously. Else we # break out if s[start] == "<": if mark[start] == 0: mark[start] = 1 start -= a[start] # It will be inside forever else: possible = 0 break # If the movement is towards right, then # we move right. The start variable and # mark that position as visited if not # visited previously else we break out else: if mark[start] == 0: mark[start] = 1 start += a[start] # it will be inside forever else: possible = 0 break if possible == 0: print "it stays inside forever" else: print "comes out" # Driver code n = 2s = "><"a = [1, 2] checkingPossibility(a, n, s) |
C#
// C# Possibility of moving out of maze using System; class GFG { // Function to check whether it // will stay inside or come out static void checkingPossibility( int []a, int n, String s) { // marks all the positions that // is visited int []mark = new int[a[0] * n] ; // Initial starting point int start = 0; // initial assumption is it // comes out int possible = 1; //runs till it is inside or // comes out while( start >= 0 && start < n) { //if the movement is towards // left then we move left. // The start variable and // mark that position as // visited if not visited // previously. Else we // break out if (s == "<") { if (mark[start] == 0) { mark[start] = 1; start -= a[start] ; } // It will be inside forever else { possible = 0; break; } } // If the movement is towards // right, then we move right. // The start variable and mark // that position as visited if // not visited previously else // we break out else { if (mark[start] == 0) { mark[start] = 1; start += a[start] ; } // it will be inside forever else { possible = 0; break; } } } if (possible == 0) Console.Write( "it stays " + "inside forever"); else Console.Write("comes out"); } // Driver code public static void Main () { int n = 2; String s = "><"; int []a = {1, 2}; checkingPossibility(a, n, s); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript Possibility of moving out of maze // Function to check whether it // will stay inside or come out function checkingPossibility(a, n, s) { // marks all the positions that // is visited let mark = new Array(a[0] * n); mark.fill(0); // Initial starting point let start = 0; // initial assumption is it // comes out let possible = 1; //runs till it is inside or // comes out while(start >= 0 && start < n) { //if the movement is towards // left then we move left. // The start variable and // mark that position as // visited if not visited // previously. Else we // break out if (s == "<") { if (mark[start] == 0) { mark[start] = 1; start -= a[start] ; } // It will be inside forever else { possible = 0; break; } } // If the movement is towards // right, then we move right. // The start variable and mark // that position as visited if // not visited previously else // we break out else { if (mark[start] == 0) { mark[start] = 1; start += a[start] ; } // it will be inside forever else { possible = 0; break; } } } if (possible == 0) document.write( "it stays " + "inside forever"); else document.write("comes out"); } let n = 2; let s = "><"; let a = [1, 2]; checkingPossibility(a, n, s); </script> |
Output:
comes out
Time complexity: O(n)
Auxiliary Space: O(n) as a vector of n size is been created, since n extra space has been taken.
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
