Compruebe si es posible llegar a (X, Y) desde (1, 1) siguiendo los pasos dados

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 ⁴ ) 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:

1. Encuentre el mcd de (X, Y) y guárdelo en una variable, digamos val .
2. Compruebe si val es una potencia de 2 comprobando si (val & amp;(val-1)) es igual a 0 donde & es AND bit a bit .
3. 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++ 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 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 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# 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

<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)