Minimice las operaciones para convertir (0, 0) a (N, M) incrementando uno o ambos por K

Dados dos números enteros N y M , la tarea es calcular el número mínimo de operaciones requeridas para convertir (0, 0) a (N, M) usando las siguientes operaciones:

• Elija cualquier número entero K y convierta (x, y) en (x + K, y + K) .
• Elija cualquier número entero K y convierta (x, y) en (x – K, y + K) o (x + K, y – K) .

Ejemplos:

Entrada: N = 3, M = 5
Salida: 2
Explicación: En la primera operación, tome K = 4 y realice la primera operación, es decir, (0 + 4, 0 + 4) -> (4, 4). En la segunda operación, tome K = 1 y realice la segunda operación, es decir, (4 – 1, 4 + 1) -> (3, 5), que es el valor requerido. 

Entrada: N = 1, M = 4
Salida: -1
Explicación: No existe una secuencia posible de operaciones dadas para convertir (0, 0) a (1, 4). 

Enfoque: El problema dado se puede resolver utilizando la observación de que cada par (N, M) se puede dividir en cuatro casos siguientes:

• Caso 1, donde (N, M) = (0, 0). En tales casos, se requerirán 0 operaciones.
• Caso 2, donde N = M. En tales casos, elija K = N y realice la primera operación. Por lo tanto, solo se requiere una operación.
• Caso 3, donde N y M son de la misma paridad, es decir, N % 2 = M % 2. En tales casos, se puede observar que el número de operaciones requeridas es siempre 2.
• Caso 4, donde N y M son de diferente paridad, es decir, N % 2 != M % 2. En tales casos, no existe una secuencia posible de operaciones.

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of operations required to convert
// a pair of integers (0, 0) to (N, M)
int minOperations(int N, int M)
{
    // Case 1
    if (N == M && N == 0)
        return 0;
 
    // Case 2
    if (N == M)
        return 1;
 
    // Case 3
    if (N % 2 == M % 2)
        return 2;
 
    // Not possible
    return -1;
}
 
// Driver Code
int main()
{
    int N = 3;
    int M = 5;
    cout << minOperations(N, M);
 
    return 0;
}

// Java program to implement
// the above approach
class GFG {
 
  // Function to find the minimum number
  // of operations required to convert
  // a pair of integers (0, 0) to (N, M)
  static int minOperations(int N, int M) {
 
    // Case 1
    if (N == M && N == 0)
      return 0;
 
    // Case 2
    if (N == M)
      return 1;
 
    // Case 3
    if (N % 2 == M % 2)
      return 2;
 
    // Not possible
    return -1;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int N = 3;
    int M = 5;
    System.out.println(minOperations(N, M));
 
  }
}
 
// This code is contributed by Saurabh Jaiswal

# Python program of the above approach
 
# Function to find the minimum number
# of operations required to convert
# a pair of integers (0, 0) to (N, M)
def minOperations(N, M):
   
    # Case 1
    if N == M and N == 0:
        return 0
 
    # Case 2
    if N == M:
        return 1
 
    # Case 3
    if N % 2 == M % 2:
        return 2
 
    # Not possible
    return -1
 
# Driver Code
N = 3
M = 5
print(minOperations(N, M))
 
# This code is contributed by GFGking

// C# program to implement
// the above approach
using System;
class GFG
{
 
  // Function to find the minimum number
  // of operations required to convert
  // a pair of integers (0, 0) to (N, M)
  static int minOperations(int N, int M)
  {
     
    // Case 1
    if (N == M && N == 0)
      return 0;
 
    // Case 2
    if (N == M)
      return 1;
 
    // Case 3
    if (N % 2 == M % 2)
      return 2;
 
    // Not possible
    return -1;
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 3;
    int M = 5;
    Console.Write(minOperations(N, M));
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program of the above approach
 
    // Function to find the minimum number
    // of operations required to convert
    // a pair of integers (0, 0) to (N, M)
    const minOperations = (N, M) => {
        // Case 1
        if (N == M && N == 0)
            return 0;
 
        // Case 2
        if (N == M)
            return 1;
 
        // Case 3
        if (N % 2 == M % 2)
            return 2;
 
        // Not possible
        return -1;
    }
 
    // Driver Code
    let N = 3;
    let M = 5;
    document.write(minOperations(N, M));
 
// This code is contributed by rakeshsahni
 
</script>

2

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)