Given two integers X and Y, the task is to check if it is possible to reach (X, Y) from (1, 1) by the following possible moves:
- From a point (a, b) such that b > a, move to the to point (a, b – a).
- From a point (a, b) such that a > b, move to the to point (a – b, b).
- Move from any point (a, b) to point (2 * a, b) or (a, 2 * b).
If it is possible to reach (X, Y), print “Yes“. Otherwise, print “No”.
Examples:
Input: X = 4, Y = 7
Output: Yes
Explanation: Point (4, 7) can be reached by the following steps: (1, 1) -> (1, 2) -> (1, 4) -> (1, 8) -> (1, 7) -> (2, 7) -> (4, 7)Input: X = 3, Y = 6
Output: No
Naive Approach: The simplest approach to solve the problem is to recursively check if (1, 1) can be reached from (X, Y) by making all possible moves from a point. If the point (1, 1) is reached at any point, print “Yes”. Otherwise, print “No”.
Time Complexity: O(N4) where N is the number of steps to reach the point (1, 1).
Auxiliary Space: O(1)
Efficient Approach: The idea is to find the greatest common divisor and observe the following facts:
- By moving the point from (a, b) to the points (a, b – a) or (a – b, b), there is no change in the GCD of the pair
- By moving the point from (a, b) to the points (2 * a, b) or (a, 2 * b), GCD may get doubled or it may remain the same.
- Therefore, from the above observations, point (1, 1) can move to point (X, Y) if and only if gcd of (X, Y) is a power of 2.
Follow the steps below to solve the above approach:
- Find the gcd of (X, Y) and store it in a variable, say val.
- Check if val is a power of 2 by checking if (val & amp;(val-1)) is equal to 0 where & is bitwise AND.
- If it is a power of two print “Yes”. 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 numbersint gcd(int a, int b){ // Base case if (a < b) { int t = a; a = b; b = t; } if (a % b == 0) return b; // Recurse return gcd(b, a % b);}// Function to print the answervoid printAnswer(int x, int y){ // GCD of X and Y int val = gcd(x, y); // If GCD is power of 2 if ((val & (val - 1)) == 0) cout << "Yes"; else cout << "No";}// Driver code int main(){ // Given X and Y int x = 4; int y = 7; // Function call printAnswer(x, y); return 0;}// This code is contributed by RohitOberoi |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the gcd of two numbers public static int gcd(int a, int b) { // Base case if (a < b) { int t = a; a = b; b = t; } if (a % b == 0) return b; // Recurse return gcd(b, a % b); } // Function to print the answer static void printAnswer(int x, int y) { // GCD of X and Y int val = gcd(x, y); // If GCD is power of 2 if ((val & (val - 1)) == 0) System.out.println("Yes"); else System.out.println("No"); } // Driver code public static void main(String[] args) { // Given X and Y int x = 4; int y = 7; // Function call printAnswer(x, y); }} |
Python3
# Python3 program for the# above approach# Function to find the gcd # of two numbersdef gcd(a, b): # Base case if (a < b): t = a a = b b = t if (a % b == 0): return b # Recurse return gcd(b, a % b)# Function to print the # answerdef printAnswer(x, y): # GCD of X and Y val = gcd(x, y) # If GCD is power of 2 if ((val & (val - 1)) == 0): print("Yes") else: print("No")# Driver codeif __name__ == "__main__": # Given X and Y x = 4 y = 7 # Function call printAnswer(x, y)# This code is contributed by Chitranayal |
C#
// C# program for the above approachusing System;class GFG{// Function to find the gcd of two numberspublic static int gcd(int a, int b){ // Base case if (a < b) { int t = a; a = b; b = t; } if (a % b == 0) return b; // Recurse return gcd(b, a % b);}// Function to print the answerstatic void printAnswer(int x, int y){ // GCD of X and Y int val = gcd(x, y); // If GCD is power of 2 if ((val & (val - 1)) == 0) Console.WriteLine("Yes"); else Console.WriteLine("No");}// Driver codepublic static void Main(){ // Given X and Y int x = 4; int y = 7; // Function call printAnswer(x, y);}}// This code is contributed by bgangwar59 |
Javascript
<script>// JavaScript program for the above approach// Function to find the gcd of// two numbersfunction gcd(a, b){ // Base case if (a < b) { let t = a; a = b; b = t; } if (a % b == 0) return b; // Recurse return gcd(b, a % b);}// Function to print the answerfunction printAnswer(x, y){ // GCD of X and Y let val = gcd(x, y); // If GCD is power of 2 if ((val & (val - 1)) == 0) document.write("Yes"); else document.write("No");}// Driver code // Given X and Y let x = 4; let y = 7; // Function call printAnswer(x, y);// This code is contributed by Surbhi Tyagi.</script> |
Yes
Time Complexity: O(Log(min(X, Y))) where (X, Y) is the given point.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More Info here to that Topic: geeksforgeeks.org/check-if-it-is-possible-to-reach-x-y-from-1-1-by-given-steps/ […]
… [Trackback]
[…] Find More Info here on that Topic: geeksforgeeks.org/check-if-it-is-possible-to-reach-x-y-from-1-1-by-given-steps/ […]