Dados dos enteros X e Y , la tarea es verificar si es posible llegar a (X, Y) desde (1, 1 ) mediante los siguientes movimientos posibles:
- Desde un punto (a, b) tal que b > a , muévete hasta el punto (a, b – a) .
- Desde un punto (a, b) tal que a > b , muévete hasta el punto (a – b, b) .
- Mover desde cualquier punto (a, b) al punto (2 * a, b) o (a, 2 * b) .
Si es posible llegar a (X, Y), escriba “ Sí ”. De lo contrario, escriba “No” .
Ejemplos:
Entrada: X = 4, Y = 7
Salida: Sí
Explicación: Se puede llegar al punto (4, 7) mediante los siguientes pasos: (1, 1) -> (1, 2) -> (1, 4) -> ( 1, 8) -> (1, 7) -> (2, 7) -> (4, 7)Entrada: X = 3, Y = 6
Salida: No
Enfoque ingenuo: el enfoque más simple para resolver el problema es verificar recursivamente si se puede llegar a (1, 1) desde (X, Y) haciendo todos los movimientos posibles desde un punto. Si se alcanza el punto (1, 1) en cualquier punto, escriba «Sí» . De lo contrario, escriba “No” .
Complejidad Temporal: O(N 4 ) donde N es el número de pasos para llegar al punto (1, 1).
Espacio Auxiliar: O(1)
Enfoque Eficiente: La idea es encontrar el máximo común divisor y observar los siguientes hechos:
- Al mover el punto de (a, b) a los puntos (a, b – a) o (a – b, b) , no hay cambio en el MCD del par
- Al mover el punto de (a, b) a los puntos (2 * a, b) o (a, 2 * b) , GCD puede duplicarse o permanecer igual.
- Por lo tanto, a partir de las observaciones anteriores, el punto (1, 1) puede moverse al punto (X, Y) si y solo si mcd de (X, Y) es una potencia de 2 .
Siga los pasos a continuación para resolver el enfoque anterior:
- Encuentre el mcd de (X, Y) y guárdelo en una variable, digamos val .
- Compruebe si val es una potencia de 2 comprobando si (val & amp;(val-1)) es igual a 0 donde & es AND bit a bit .
- Si es una potencia de dos, escriba «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find the gcd of // two numbers 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 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) 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 approach import 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 numbers def 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 # answer def 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 code if __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 approach using System; 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) Console.WriteLine("Yes"); else Console.WriteLine("No"); } // Driver code public 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 numbers function 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 answer function 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
Complejidad de tiempo: O(Log(min(X, Y))) donde (X, Y) es el punto dado.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA