Given two positive integers X and Y, the task is to check if it is possible to reach (X, Y) from (1, 0) by the given steps. In each step, possible moves from any cell (a, b) are (a, b + a) or (a + b, b). Print “Yes” if possible. Otherwise, print “No”.
Examples:
Input: X = 2, Y = 7
Output: Yes
Explanation: Sequence of moves to reach (2, 7) are: (1, 0) -> (1, 1) -> (2, 1) -> (2, 3) -> (2, 5) -> (2, 7).Input: X = 30, Y = 24
Output: No
Naive Approach: The simplest approach is to try to move from points (X, Y) to (1, 0) recursively by using the operation (X – Y, Y) or (X, Y – X) until it becomes equals to (1, 0). If the X-coordinate becomes less than 1 or Y-coordinate becomes less than 0, then it is not possible to reach (1, 0). Therefore, print “No”. Otherwise, if (1, 0) is reached, print “Yes”.
Time Complexity: O(2log (min(X, Y)))
Auxiliary Space: O(1)
Efficient Approach: The idea is to observe the following properties:
- Try to solve the problem in reverse order i.e., it is possible to move from (X, Y) to (1, 0) by recursively moving to points (X – Y, Y) or (X, Y – X).
- The above property can be represented as follows:
GCD(X, Y) = GCD(X, Y – X) or GCD(X – Y, Y)
where,
Base Case is GCD(X, 0) = X
Now, notice that gcd of 1 and 0 i.e., gcd(1, 0) is 1.
Therefore, gcd of X and Y must also be 1 to reach (1, 0).
Therefore, from the above observations, the path from (1, 0) to (X, Y) always exists if GCD(X, Y) = 1. Print “Yes” if the GCD of the given two numbers is 1. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find the GCD of two// numbers a and bint GCD(int a, int b){ // Base Case if (b == 0) return a; // Recursively find the GCD else return GCD(b, a % b);}// Function to check if (x, y) can be// reached from (1, 0) from given movesvoid check(int x, int y){ // If GCD is 1, then print "Yes" if (GCD(x, y) == 1) { cout << "Yes"; } else { cout << "No"; }}// Driver Codeint main(){ // Given X and Y int X = 2, Y = 7; // Function call check(X, Y); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class GFG{// Function to find the // GCD of two numbers a // and bstatic int GCD(int a, int b){ // Base Case if (b == 0) return a; // Recursively find // the GCD else return GCD(b, a % b);}// Function to check if // (x, y) can be reached // from (1, 0) from given // movesstatic void check(int x, int y){ // If GCD is 1, then // print "Yes" if (GCD(x, y) == 1) { System.out.print("Yes"); } else { System.out.print("No"); }}// Driver Codepublic static void main(String[] args){ // Given X and Y int X = 2, Y = 7; // Function call check(X, Y);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to find the GCD of two# numbers a and bdef GCD(a, b): # Base Case if (b == 0): return a # Recursively find the GCD else: return GCD(b, a % b)# Function to check if (x, y) can be# reached from (1, 0) from given movesdef check(x, y): # If GCD is 1, then print"Yes" if (GCD(x, y) == 1): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': # Given X and Y X = 2 Y = 7 # Function call check(X, Y)# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;class GFG{ // Function to find the // GCD of two numbers a // and bstatic int GCD(int a, int b){ // Base Case if (b == 0) return a; // Recursively find // the GCD else return GCD(b, a % b);}// Function to check if // (x, y) can be reached // from (1, 0) from given // movesstatic void check(int x, int y){ // If GCD is 1, then // print "Yes" if (GCD(x, y) == 1) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); }}// Driver Codepublic static void Main(){ // Given X and Y int X = 2, Y = 7; // Function call check(X, Y);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// JavaScript program for the above approach// Function to find the GCD of two// numbers a and bfunction GCD(a, b){ // Base Case if (b == 0) return a; // Recursively find the GCD else return GCD(b, a % b);}// Function to check if (x, y) can be// reached from (1, 0) from given movesfunction check(x, y){ // If GCD is 1, then print "Yes" if (GCD(x, y) == 1) { document.write("Yes"); } else { document.write("No"); }}// Driver Code // Given X and Y let X = 2, Y = 7; // Function call check(X, Y);// This code is contributed by Surbhi Tyagi.</script> |
Yes
Time Complexity: O(log(min(X, Y))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
