Given two integers X and Y, which represent the number of rows and columns respectively of a matrix, the task is to check whether there exists a path, Which follows all the below conditions:
- Starting of the path is from the cell (1, 1).
- Ending of the path is any cell adjacent to (1, 1).
- You have to traverse each cell of the matrix only once.
Note: Here 1 based indexing is used.
Examples:
Input: X = 2, Y = 3
Output: YES
Explanation:
Explanation for input test case
Each cell is traversed once, starting cell is (1, 1) and ending cell is (2, 1), Which is adjacent to (1, 1). Hence, all the conditions met.
Input: X = 1, Y = 1
Output: NO
Explanation: As there is no adjacent cell of ( 1, 1 ) exists therefore, Output is NO.
Approach: The problem can be solved based on the following observation:
Observation:
Let’s take some random test-cases.
Test case 1: X = 4, Y = 4
Output: YES
Explanation:Explanation for test case 1
Test case 2: X=4, Y=5
Output: YES
Explanation:Explanation for test case 2
Test case 3: X = 1, Y =3
Output: NO
Explanation: No path is possible that satisfy given constraints.From all above test cases, We can conclude some conditions:
- If both X and Y are odd, Then there exists no path.
- If (X = 1 && Y > 2) or (Y = 1 && X > 2), Then no path exists.
- All the cases except above discussed 2( number 1 and number 2 ) cases will have a path.
Follow the below steps to implement the idea:
- Check the conditions on X and Y discussed above.
- If the values match any of the first two conditions then no path is possible.
- Otherwise, there exists a path.
Below is the implementation of the above approach.
C++
// C++ implementation#include <iostream>using namespace std;// Function to check existence of pathstring Is_Path_Possible(long X, long Y){ // Testing and printing output on the // basis of discussed conditions if (X % 2 != 0 && Y % 2 != 0 || X == 1 && Y > 2 || Y == 1 && X > 2) { return "NO"; } else { return "YES"; }}int main(){ long X = 2, Y = 2; // Function call cout << (Is_Path_Possible(X, Y)); return 0;}// This code is contributed by ksam24000 |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Driver code public static void main(String args[]) { long X = 2, Y = 2; // Function call System.out.println(Is_Path_Possible(X, Y)); } // Function to check existence of path static String Is_Path_Possible(long X, long Y) { // Testing and printing output on the // basis of discussed conditions if (X % 2 != 0 && Y % 2 != 0 || X == 1 && Y > 2 || Y == 1 && X > 2) { return "NO"; } else { return "YES"; } }} |
Python3
# Python code to implement the approachdef Is_Path_Possible(X, Y): if(X % 2 != 0 and Y % 2 != 0 or X == 1 and Y > 2 or Y == 1 and X > 2): return "NO" else: return "YES"X, Y = 2, 2# Function callprint(Is_Path_Possible(X, Y))# This code is contributed by lokesh |
C#
// C# code to implement the above approachusing System;public class GFG { // Driver code public static void Main(string []args) { long X = 2, Y = 2; // Function call Console.WriteLine(Is_Path_Possible(X, Y)); } // Function to check existence of path static String Is_Path_Possible(long X, long Y) { // Testing and printing output on the // basis of discussed conditions if (X % 2 != 0 && Y % 2 != 0 || X == 1 && Y > 2 || Y == 1 && X > 2) { return "NO"; } else { return "YES"; } }}// This code is contributed by AnkThon |
Javascript
// JavaScript code to implement the approach// Function to check existence of pathconst Is_Path_Possible = (X, Y) => { // Testing and printing output on the // basis of discussed conditions if (X % 2 != 0 && Y % 2 != 0 || X == 1 && Y > 2 || Y == 1 && X > 2) { return "NO"; } else { return "YES"; }}// Driver codelet X = 2, Y = 2;// Function callconsole.log(Is_Path_Possible(X, Y));// This code is contributed by rakeshsahni |
YES
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
