Pasos mínimos para convertir X en Y mediante división y multiplicación repetidas

Dados dos enteros X e Y , la tarea es encontrar el número mínimo de pasos para convertir el entero X a Y usando cualquiera de las operaciones en cada paso: 

• Dividir el número por cualquier número natural
• Multiplicar el número con cualquier número natural

Ejemplos: 

Entrada: X = 8, Y = 12 
Salida: 2 
Explicación: 
Primero divide 8 por 2: 8/2 = 4 
Luego multiplica por 3: 4*3 = 12

Entrada: X = 4, Y = 8 
Salida: 1 
Explicación: 
Para convertir 4 a 8, multiplique 4 por 2: 4 * 2 = 8 

Enfoque: Para resolver el problema mencionado anteriormente: 

• Asegúrese de que X contenga el valor más pequeño entre X e Y. Ahora, si X es mayor que Y , entonces sabemos que siempre es más fácil cambiar un número más pequeño a un número más grande. Por lo tanto, simplemente intercambiamos los valores de X e Y y luego seguimos los pasos que se mencionan a continuación.
• Si ambos números enteros son iguales , la respuesta será cero ya que no se realiza ninguna conversión.
  Por ejemplo,

If X = 4, Y = 4

Here 4 = 4
Therefore, answer = 0
(as they both are already same)

• Sin embargo, si X es menor que Y entonces: 
  • tenemos que comprobar que Y % X da 0 o no.
  • En caso afirmativo, Y se puede representar como X * (Y / X) y obtenemos el resultado deseado en un solo paso.
    Por ejemplo,

If X = 4, Y = 12

Here 12 % 4 = 0
Therefore, answer = 1
(4 * 3 = 12)

• De lo contrario, la respuesta será 2 ya que toma dos pasos, uno para la división (X = X/X) y otro para la multiplicación (X = X * Y).
  Por ejemplo,

If X = 8, Y = 13

Here 13 % 8 != 0
Therefore, 
1. X = X/X = 8/8 = 1
2. X = X*Y = 1*13 = 13

Hence, answer = 2

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

// C++ implementation to find minimum
// steps to convert X to Y by repeated
// division and multiplication
 
#include <bits/stdc++.h>
using namespace std;
 
int solve(int X, int Y)
{
    // Check if X is greater than Y
    // then swap the elements
    if (X > Y) {
        int temp = X;
        X = Y;
        Y = temp;
    }
 
    // Check if X equals Y
    if (X == Y)
        cout << 0 << endl;
 
    else if (Y % X == 0)
        cout << 1 << endl;
    else
        cout << 2 << endl;
}
 
// Driver code
int main()
{
    int X = 8, Y = 13;
    solve(X, Y);
 
    return 0;
}

// Java implementation to find minimum
// steps to convert X to Y by repeated
// division and multiplication
class GFG{
 
static int solve(int X, int Y)
{
    // Check if X is greater than Y
    // then swap the elements
    if (X > Y)
    {
        int temp = X;
        X = Y;
        Y = temp;
    }
 
    // Check if X equals Y
    if (X == Y)
        System.out.println(0 );
 
    else if (Y % X == 0)
        System.out.println( 1 );
    else
        System.out.println(2 );
        return 0;
}
 
// Driver code
public static void main(String args[])
{
    int X = 8, Y = 13;
    solve(X, Y);
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 implementation to find minimum
# steps to convert X to Y by repeated
# division and multiplication
def solve(X, Y):
     
    # Check if X is greater than Y
    # then swap the elements
    if (X > Y):
        temp = X
        X = Y
        Y = temp
   
    # Check if X equals Y
    if (X == Y):
        print(0)
   
    elif (Y % X == 0):
        print(1)
    else:
        print(2)
  
# Driver code
X = 8
Y = 13
 
solve(X, Y)
 
# This code is contributed by code_hunt

// C# implementation to find minimum
// steps to convert X to Y by repeated
// division and multiplication
using System;
 
class GFG{
 
static int solve(int X, int Y)
{
     
    // Check if X is greater than Y
    // then swap the elements
    if (X > Y)
    {
        int temp = X;
        X = Y;
        Y = temp;
    }
 
    // Check if X equals Y
    if (X == Y)
        Console.WriteLine(0);
 
    else if (Y % X == 0)
        Console.WriteLine(1);
    else
        Console.WriteLine(2);
    return 0;
}
 
// Driver code
public static void Main(String[] args)
{
    int X = 8, Y = 13;
    solve(X, Y);
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
    // Javascript implementation to find minimum
    // steps to convert X to Y by repeated
    // division and multiplication
     
    function solve(X, Y)
    {
        // Check if X is greater than Y
        // then swap the elements
        if (X > Y) {
            let temp = X;
            X = Y;
            Y = temp;
        }
 
        // Check if X equals Y
        if (X == Y)
            document.write(0);
 
        else if (Y % X == 0)
            document.write(1);
        else
            document.write(2);
    }
     
    let X = 8, Y = 13;
    solve(X, Y);
 
 
</script>

2

Complejidad de tiempo: O(1), ya que estamos usando solo operaciones de tiempo constante.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.