Operaciones mínimas requeridas para hacer dos números iguales

Dados dos enteros A y B . la tarea es encontrar el número mínimo de operaciones requeridas para hacer que A y B sean iguales. En cada operación, se puede realizar cualquiera de los siguientes pasos: 
 

• Incrementa A o B con su valor inicial.
• Incrementa tanto A como B con su valor inicial

Ejemplos: 
 

Entrada: A = 4, B = 10 
Salida: 4 
Explicación: 
Inicialmente A = 4, B = 10 
Operación 1: Solo incremento A: A = A + 4 = 8 
Operación 2: Solo incremento A: A = A + 4 = 12 
Operación 3: Solo incremento A: A = A + 4 = 16 
Operación 4: Incremento A y B: A = A + 4 = 20 y B = B + 10 = 20 
Ahora son iguales.
Entrada: A = 7, B = 23 
Salida: 22 
Explicación: 
Inicialmente A = 7, B = 23 
Operación 1 – 7: Incremento A y B: A = 56 y B = 161 
Operación 8 – 22: Incremento A: A = 161 y B = 161 
Son iguales ahora. 
 

Enfoque: Este problema se puede resolver usando GCD . 
 

1. Si A es mayor que B, entonces intercambia A y B.
2. Ahora reduzca B, de modo que el mcd de A y B se convierta en 1.
3. Por lo tanto, las operaciones mínimas requeridas para alcanzar el mismo valor son (B – 1).

Por ejemplo: Si A = 4, B = 10: 
 

• Paso 1: Compara 4 y 10, ya que siempre necesitamos B como el valor mayor. Aquí ya B es mayor que A. Entonces, ahora no se requiere intercambio.
• Paso 2: MCD(4, 10) = 2. Entonces, reducimos B a B/2. Ahora A = 4 y B = 5. 
  GCD(4, 5) = 1, que era el objetivo.
• Paso 3: (Valor actual de B – 1) será el conteo requerido. Aquí, Actual B = 5. Entonces (5 – 1 = 4), es decir, se requieren un total de 4 operaciones.

A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program to find minimum
// operations required to
// make two numbers equal
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// minimum operations required
long long int minOperations(
    long long int A,
    long long int B)
{
 
    // Keeping B always greater
    if (A > B)
        swap(A, B);
 
    // Reduce B such that
    // gcd(A, B) becomes 1.
    B = B / __gcd(A, B);
 
    return B - 1;
}
 
// Driver code
int main()
{
    long long int A = 7, B = 15;
 
    cout << minOperations(A, B)
         << endl;
 
    return 0;
}

// Java program to find minimum
// operations required to
// make two numbers equal
class GFG{
  
// Function to return the
// minimum operations required
static int  minOperations(
    int  A,
    int  B)
{
  
    // Keeping B always greater
    if (A > B) {
        A = A+B;
        B = A-B;
        A = A-B;
    }
  
    // Reduce B such that
    // gcd(A, B) becomes 1.
    B = B / __gcd(A, B);
  
    return B - 1;
}
static int __gcd(int a, int b) 
{ 
    return b == 0? a:__gcd(b, a % b);    
}
 
// Driver code
public static void main(String[] args)
{
    int  A = 7, B = 15;
  
    System.out.print(minOperations(A, B)
         +"\n");
  
}
}
 
// This code contributed by sapnasingh4991

# Python program to find minimum
# operations required to
# make two numbers equal
import math
 
# Function to return the
# minimum operations required
def minOperations(A, B):
 
    # Keeping B always greater
    if (A > B):
        swap(A, B)
 
    # Reduce B such that
    # gcd(A, B) becomes 1.
    B = B // math.gcd(A, B);
 
    return B - 1
 
# Driver code
A = 7
B = 15
 
print(minOperations(A, B))
 
# This code is contributed by Sanjit_Prasad

// C# program to find minimum
// operations required to
// make two numbers equal
using System;
 
class GFG{
   
// Function to return the
// minimum operations required
static int  minOperations(
    int  A,
    int  B)
{
   
    // Keeping B always greater
    if (A > B) {
        A = A+B;
        B = A-B;
        A = A-B;
    }
   
    // Reduce B such that
    // gcd(A, B) becomes 1.
    B = B / __gcd(A, B);
   
    return B - 1;
}
static int __gcd(int a, int b) 
{ 
    return b == 0? a:__gcd(b, a % b);    
}
  
// Driver code
public static void Main(String[] args)
{
    int  A = 7, B = 15;
   
    Console.Write(minOperations(A, B)
         +"\n");
}
}
 
// This code is contributed by sapnasingh4991

<script>
// javascript program to find minimum
// operations required to
// make two numbers equal   
// Function to return the
    // minimum operations required
    function minOperations(A, B)
{
 
        // Keeping B always greater
        if (A > B) {
            A = A + B;
            B = A - B;
            A = A - B;
        }
 
        // Reduce B such that
        // gcd(A, B) becomes 1.
        B = B / __gcd(A, B);
 
        return B - 1;
    }
 
    function __gcd(a , b) {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Driver code
        var A = 7, B = 15;
        document.write(minOperations(A, B) + "\n");
 
// This code is contributed by Rajput-Ji
</script>

14

Complejidad del tiempo: O(log(max(A, B))

Espacio auxiliar: O(log(max(A, B))