Given a pair of coordinates (X1, Y1)(source) and (X2, Y2)(destination), the task is to check if it is possible to reach the destination form the source by the following movements from any cell (X, Y):
- (X + Y, Y)
- (X, Y + X)
Note: All coordinates are positive and can be as large as 1018.
Examples:
Input: X1 = 2, Y1 = 10, X2 = 26, Y2 = 12Â
Output: YesExplanation: Possible path: (2, 10) ? (2, 12) ? (14, 12) ? (26, 12)
Therefore, a path exists between source and destination.Input: X1 = 20, Y1 = 10, X2 = 6, Y2 = 12Â
Output: No
Naive Approach: The simplest approach to solve the problem is by using recursion. Refer to the article check if a destination is reachable from source with two movements allowed for the recursive approach.
Efficient Approach: The main idea is to check if a path from the destination coordinates (X2, Y2) to the source (X1, Y1) exists or not.
Follow the steps below to solve the problem:
- Keep subtracting the smallest of (X2, Y2) from the largest of (X2, Y2) and stop if X2 becomes less than X1 or Y2 becomes less than Y1.
- Now, compare (X1, Y1) and modified (X2, Y2). If X1 is equal to X2 and Y1 is equal to Y2, then print “Yes“.
- If X1 is not equal to X2 or Y1 is equal, not Y2, then print “No“.
To optimize the complexity of the subtraction operation, the modulus operation can be used instead. Simply perform x2 = x2 % y2 and y2 = y2 % x2 and check for the necessary condition mentioned above.
C++
// C++ program to implement// the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Check if (x2, y2) can be reached// from (x1, y1)bool isReachable(long long x1, long long y1,                 long long x2, long long y2){    while (x2 > x1 && y2 > y1) {Â
        // Reduce x2 by y2 until it is        // less than or equal to x1        if (x2 > y2)            x2 %= y2;Â
        // Reduce y2 by x2 until it is        // less than or equal to y1        else            y2 %= x2;    }Â
    // If x2 is reduced to x1    if (x2 == x1)Â
        // Check if y2 can be        // reduced to y1 or not        return (y2 - y1) >= 0               && (y2 - y1) % x1 == 0;Â
    // If y2 is reduced to y1    else if (y2 == y1)Â
        // Check if x2 can be        // reduced to x1 or not        return (x2 - x1) >= 0               && (x2 - x1) % y1 == 0;    else        return 0;}Â
// Driver Codeint main(){Â Â Â Â long long source_x = 2, source_y = 10;Â Â Â Â long long dest_x = 26, dest_y = 12;Â
    if (isReachable(source_x, source_y,                    dest_x, dest_y))        cout << "Yes";    else        cout << "No";    return 0;} |
Python3
# Python3 program to implement# the above approachÂ
# Check if (x2, y2) can be reached# from (x1, y1)def isReachable(x1, y1, x2, y2):Â
    while(x2 > x1 and y2 > y1):Â
        # Reduce x2 by y2 until it is        # less than or equal to x1        if(x2 > y2):            x2 %= y2Â
        # Reduce y2 by x2 until it is        # less than or equal to y1        else:            y2 %= x2Â
    # If x2 is reduced to x1    if(x2 == x1):Â
        # Check if y2 can be        # reduced to y1 or not        return (y2 - y1) >= 0 and (                y2 - y1) % x1 == 0Â
    # If y2 is reduced to y1    elif(y2 == y1):Â
        # Check if x2 can be        # reduced to x1 or not         return (x2 - x1) >= 0 and (                x2 - x1) % y1 == 0    else:        return 0Â
# Driver Codesource_x = 2source_y = 10dest_x = 26dest_y = 12Â
# Function callif(isReachable(source_x, source_y,                 dest_x, dest_y)):    print("Yes")else:    print("No")Â
# This code is contributed by Shivam Singh |
Java
// Java program to implement// the above approachclass GFG{Â
// Check if (x2, y2) can be reached// from (x1, y1)static boolean isReachable(long x1, long y1,                           long x2, long y2){    while (x2 > x1 && y2 > y1)     {        // Reduce x2 by y2 until it is        // less than or equal to x1        if (x2 > y2)            x2 %= y2;Â
        // Reduce y2 by x2 until it is        // less than or equal to y1        else            y2 %= x2;    }Â
    // If x2 is reduced to x1    if (x2 == x1)Â
        // Check if y2 can be        // reduced to y1 or not        return (y2 - y1) >= 0 &&                (y2 - y1) % x1 == 0;Â
    // If y2 is reduced to y1    else if (y2 == y1)Â
        // Check if x2 can be        // reduced to x1 or not        return (x2 - x1) >= 0 &&                (x2 - x1) % y1 == 0;    else        return false;}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â long source_x = 2, source_y = 10;Â Â Â Â long dest_x = 26, dest_y = 12;Â
    if (isReachable(source_x, source_y,                    dest_x, dest_y))        System.out.print("Yes");    else        System.out.print("No");}}Â
// This code is contributed by shikhasingrajput |
C#
// C# program to implement// the above approachusing System;class GFG{Â
// Check if (x2, y2) can be reached// from (x1, y1)static bool isReachable(long x1, long y1,                        long x2, long y2){  while (x2 > x1 &&          y2 > y1)   {    // Reduce x2 by y2     // until it is less     // than or equal to x1    if (x2 > y2)      x2 %= y2;Â
    // Reduce y2 by x2     // until it is less     // than or equal to y1    else      y2 %= x2;  }Â
  // If x2 is reduced to x1  if (x2 == x1)Â
    // Check if y2 can be    // reduced to y1 or not    return (y2 - y1) >= 0 &&            (y2 - y1) % x1 == 0;Â
  // If y2 is reduced to y1  else if (y2 == y1)Â
    // Check if x2 can be    // reduced to x1 or not    return (x2 - x1) >= 0 &&            (x2 - x1) % y1 == 0;  else    return false;}Â
// Driver Codepublic static void Main(String[] args){Â Â long source_x = 2, source_y = 10;Â Â long dest_x = 26, dest_y = 12;Â
  if (isReachable(source_x, source_y,                  dest_x, dest_y))    Console.Write("Yes");  else    Console.Write("No");}}Â
// This code is contributed by shikhasingrajput |
Javascript
<script>Â
// JavaScript program for//the above approachÂ
// Check if (x2, y2) can be reached// from (x1, y1)function isReachable(x1, y1, x2, y2){    while (x2 > x1 && y2 > y1)    {        // Reduce x2 by y2 until it is        // less than or equal to x1        if (x2 > y2)            x2 %= y2;          // Reduce y2 by x2 until it is        // less than or equal to y1        else            y2 %= x2;    }      // If x2 is reduced to x1    if (x2 == x1)          // Check if y2 can be        // reduced to y1 or not        return (y2 - y1) >= 0 &&               (y2 - y1) % x1 == 0;      // If y2 is reduced to y1    else if (y2 == y1)          // Check if x2 can be        // reduced to x1 or not        return (x2 - x1) >= 0 &&               (x2 - x1) % y1 == 0;    else        return false;}  // Driver CodeÂ
    let source_x = 2, source_y = 10;    let dest_x = 26, dest_y = 12;      if (isReachable(source_x, source_y,                    dest_x, dest_y))        document.write("Yes");    else       document.write("No");   </script> |
Output:Â
Yes
Time Complexity: O(1)Â
Auxiliary Space: O(1)Â
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!
