Compruebe si es posible pasar de la coordenada dada a la coordenada deseada

Dadas dos coordenadas (x, y) y (a, b). Encuentra si es posible llegar a (x, y) desde (a, b). 

Sólo son posibles los movimientos desde cualquier coordenada (i, j). 

• (ij, j)
• (yo, ij)
• (i+j,j)
• (yo, yo+j)

Dado x, y, a, b pueden ser negativos.

Ejemplos: 

Input : (x, y) = (1, 1) and  (a, b) = (2, 3).
Output : Yes.
(1, 1) -> (2, 1) -> (2, 3).

Input : (x, y) = (2, 1) and  (a, b) = (2, 3).
Output : Yes.

Input : (x, y) = (35, 15) and  (a, b) = (20, 25).
Output : Yes.
(35, 15) -> (20, 15) -> (5, 15) -> (5, 10) -> (5, 5) ->
(10, 5) -> (15, 5) -> (20, 5) -> (20, 25)

Si observamos más de cerca el problema, podemos notar que los movimientos son pasos similares del algoritmo euclidiano para encontrar GCD . Entonces, solo es posible llegar a la coordenada (a, b) desde (x, y) si el MCD de x, y es igual al MCD de a, b. De lo contrario, no es posible.

Sea mcd de (x, y) mcd. Desde (x, y), podemos llegar a (mcd, mcd) y desde este punto, podemos llegar a (a, b) si y solo si el MCD de ‘a’ y ‘b’ también es mcd.

A continuación se muestra la implementación de este enfoque: 

// C++ program to check if it is possible to reach
// (a, b) from (x, y).
#include <bits/stdc++.h>
using namespace std;
 
// Returns GCD of i and j
int gcd(int i, int j)
{
    if (i == j)
        return i;
 
    if (i > j)
        return gcd(i - j, j);
    return gcd(i, j - i);
}
 
// Returns true if it is possible to go to (a, b)
// from (x, y)
bool ispossible(int x, int y, int a, int b)
{
    // Find absolute values of all as sign doesn't
    // matter.
    x = abs(x), y = abs(y), a = abs(a), b = abs(b);
 
    // If gcd is equal then it is possible to reach.
    // Else not possible.
    return (gcd(x, y) == gcd(a, b));
}
 
// Driven Program
int main()
{
    // Converting coordinate into positive integer
    int x = 35, y = 15;
    int a = 20, b = 25;
    (ispossible(x, y, a, b)) ? (cout << "Yes") : (cout << "No");
    return 0;
}

// Java program to check if it is possible
// to reach (a, b) from (x, y).
class GFG {
 
    // Returns GCD of i and j
    static int gcd(int i, int j)
    {
        if (i == j)
            return i;
 
        if (i > j)
            return gcd(i - j, j);
        return gcd(i, j - i);
    }
 
    // Returns true if it is possible to go to (a, b)
    // from (x, y)
    static boolean ispossible(int x, int y, int a, int b)
    {
 
        // Find absolute values of all as
        // sign doesn't matter.
        x = Math.abs(x);
        y = Math.abs(y);
        a = Math.abs(a);
        b = Math.abs(b);
 
        // If gcd is equal then it is possible to reach.
        // Else not possible.
        return (gcd(x, y) == gcd(a, b));
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Converting coordinate into positive integer
        int x = 35, y = 15;
        int a = 20, b = 25;
        if (ispossible(x, y, a, b))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}
// This code is contributed by Anant Agarwal.

# Python program to check if it is possible to reach
# (a, b) from (x, y).
# Returns GCD of i and j
def gcd(i, j):
    if (i == j):
        return i
  
    if (i > j):
        return gcd(i - j, j)
    return gcd(i, j - i)
  
# Returns true if it is possible to go to (a, b)
# from (x, y)
def ispossible(x, y, a, b):
    # Find absolute values of all as sign doesn't
    # matter.
    x, y, a, b = abs(x), abs(y), abs(a), abs(b)
  
    # If gcd is equal then it is possible to reach.
    # Else not possible.
    return (gcd(x, y) == gcd(a, b))
  
# Driven Program
    # Converting coordinate into positive integer
x, y = 35, 15
a, b = 20, 25
if(ispossible(x, y, a, b)):
    print ("Yes")
else:
    print ("No")
# Contributed by Afzal Ansari

// C# program to check if it is possible
// to reach (a, b) from (x, y).
using System;
 
class GFG {
 
    // Returns GCD of i and j
    static int gcd(int i, int j)
    {
        if (i == j)
            return i;
 
        if (i > j)
            return gcd(i - j, j);
        return gcd(i, j - i);
    }
 
    // Returns true if it is possible
    // to go to (a, b) from (x, y)
    static bool ispossible(int x, int y,
                           int a, int b)
    {
 
        // Find absolute values of all as
        // sign doesn't matter.
        x = Math.Abs(x);
        y = Math.Abs(y);
        a = Math.Abs(a);
        b = Math.Abs(b);
 
        // If gcd is equal then it is possible
        // to reach. Else not possible.
        return (gcd(x, y) == gcd(a, b));
    }
 
    // Driver code
    public static void Main()
    {
 
        // Converting coordinate
        // into positive integer
        int x = 35, y = 15;
        int a = 20, b = 25;
         
        if (ispossible(x, y, a, b))
            Console.Write("Yes");
        else
            Console.Write("No");
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to check if it
// is possible to reach
// (a, b) from (x, y).
 
// Returns GCD of i and j
function gcd($i, $j)
{
    if ($i == $j)
        return $i;
 
    if ($i > $j)
        return gcd($i - $j, $j);
    return gcd($i, $j - $i);
}
 
// Returns true if it is
// possible to go to (a, b)
// from (x, y)
function ispossible($x, $y, $a, $b)
{
     
    // Find absolute values
    // of all as sign doesn't
    // matter.
    $x = abs($x);
    $y = abs($y);
    $a = abs($a);
    $b = abs($b);
 
    // If gcd is equal then
    // it is possible to reach.
    // Else not possible.
    return (gcd($x, $y) == gcd($a, $b));
}
 
// Driver Code
{
     
    // Converting coordinate
    // into positive integer
    $x = 35; $y = 15;
    $a = 20; $b = 25;
    if (ispossible($x, $y, $a, $b))
        echo( "Yes");
    else
        echo( "No");
    return 0;
}
 
// This code is contributed by nitin mittal.
?>

<script>
// javascript program to check if it is possible
// to reach (a, b) from (x, y).   
// Returns GCD of i and j
    function gcd(i , j) {
        if (i == j)
            return i;
 
        if (i > j)
            return gcd(i - j, j);
        return gcd(i, j - i);
    }
 
    // Returns true if it is possible to go to (a, b)
    // from (x, y)
    function ispossible(x , y , a , b)
    {
 
        // Find absolute values of all as
        // sign doesn't matter.
        x = Math.abs(x);
        y = Math.abs(y);
        a = Math.abs(a);
        b = Math.abs(b);
 
        // If gcd is equal then it is possible to reach.
        // Else not possible.
        return (gcd(x, y) == gcd(a, b));
    }
 
    // Driver code
     
        // Converting coordinate into positive integer
        var x = 35, y = 15;
        var a = 20, b = 25;
        if (ispossible(x, y, a, b))
            document.write("Yes");
        else
            document.write("No");
 
// This code is contributed by todaysgaurav
</script>

Yes

Complejidad de tiempo: O(min(x, y) + min(a, b)), donde x, y, a y b son los números enteros dados.
Espacio auxiliar: O(min(x, y) + min(a, b)), espacio requerido debido a la pila de recursividad.

Este artículo es una contribución de Anuj Chauhan(anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.