Movimientos primos máximos para convertir X en Y

Dados dos enteros X e Y , la tarea es convertir X a Y usando las siguientes operaciones: 
 

1. Suma cualquier número primo a X.
2. Resta cualquier número primo de Y .

Imprime el número máximo de tales operaciones requeridas o -1 si no es posible convertir X a Y.
Ejemplos: 
 

Entrada: X = 2, Y = 4 
Salida: 1 
2 -> 4
Entrada: X = 5, Y = 6 
Salida: -1 
Es imposible convertir 5 a 6 
con las operaciones dadas. 

Enfoque: Como la tarea es maximizar las operaciones, entonces se debe agregar el mínimo valor posible a X en cada operación. Dado que el valor debe ser primo, se pueden usar los dos primos mínimos, es decir , 2 y 3 , ya que ambos son primos y pueden cubrir tanto la paridad par como la impar. Ahora, hay tres casos: 
 

• Si X > Y entonces la respuesta será -1 ya que X no puede igualarse a Y con la operación dada.
• Si X = Y entonces la respuesta será 0 .
• Si X < Y entonces calcule P = Y – X y, 
  • Si P = 1 , la respuesta será -1 , ya que 1 no es primo y no se puede sumar ni restar.
  • Si P es par, entonces 2 se puede sumar repetidamente a X y la respuesta será P / 2
  • Si P es par, agregue 3 a X y luego 2 puede agregarse repetidamente a la nueva X para que sea igual a Y , el resultado, en este caso, será 1 + ((P – 3) / 2) .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum operations
// required to convert X to Y
int maxOperations(int X, int Y)
{
 
    // X cannot be converted to Y
    if (X > Y)
        return -1;
 
    int diff = Y - X;
 
    // If the difference is 1
    if (diff == 1)
        return -1;
 
    // If the difference is even
    if (diff % 2 == 0)
        return (diff / 2);
 
    // Add 3 to X and the new
    // difference will be even
    return (1 + ((diff - 3) / 2));
}
 
// Driver code
int main()
{
    int X = 5, Y = 16;
 
    cout << maxOperations(X, Y);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the maximum operations
// required to convert X to Y
static int maxOperations(int X, int Y)
{
 
    // X cannot be converted to Y
    if (X > Y)
        return -1;
 
    int diff = Y - X;
 
    // If the difference is 1
    if (diff == 1)
        return -1;
 
    // If the difference is even
    if (diff % 2 == 0)
        return (diff / 2);
 
    // Add 3 to X and the new
    // difference will be even
    return (1 + ((diff - 3) / 2));
}
 
// Driver code
public static void main(String []args)
{
    int X = 5, Y = 16;
 
    System.out.println(maxOperations(X, Y));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function to return the maximum operations
# required to convert X to Y
def maxOperations(X, Y) :
 
    # X cannot be converted to Y
    if (X > Y) :
        return -1;
 
    diff = Y - X;
 
    # If the difference is 1
    if (diff == 1) :
        return -1;
 
    # If the difference is even
    if (diff % 2 == 0) :
        return (diff // 2);
 
    # Add 3 to X and the new
    # difference will be even
    return (1 + ((diff - 3) // 2));
 
# Driver code
if __name__ == "__main__" :
 
    X = 5; Y = 16;
 
    print(maxOperations(X, Y));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;                   
 
class GFG
{
  
// Function to return the maximum operations
// required to convert X to Y
static int maxOperations(int X, int Y)
{
  
    // X cannot be converted to Y
    if (X > Y)
        return -1;
  
    int diff = Y - X;
  
    // If the difference is 1
    if (diff == 1)
        return -1;
  
    // If the difference is even
    if (diff % 2 == 0)
        return (diff / 2);
  
    // Add 3 to X and the new
    // difference will be even
    return (1 + ((diff - 3) / 2));
}
  
// Driver code
public static void Main(String []args)
{
    int X = 5, Y = 16;
  
    Console.WriteLine(maxOperations(X, Y));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript implementation of the approach
 
// Function to return the maximum operations
// required to convert X to Y
function maxOperations(X, Y)
{
 
    // X cannot be converted to Y
    if (X > Y)
        return -1;
 
    let diff = Y - X;
 
    // If the difference is 1
    if (diff == 1)
        return -1;
 
    // If the difference is even
    if (diff % 2 == 0)
        return (diff / 2);
 
    // Add 3 to X and the new
    // difference will be even
    return (1 + ((diff - 3) / 2));
}
 
// Driver code
 
    let X = 5, Y = 16;
 
    document.write(maxOperations(X, Y));
 
// This code is contributed by _saurabh_jaiswal   
 
</script>

5

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)