Minimice las operaciones para hacer que X sea igual a Y reemplazando X con su bit a bit XOR con N

Dados dos enteros X e Y , y un entero K , la tarea es encontrar el número mínimo de operaciones para hacer que X sea igual a Y  eligiendo un número N en el rango (1 ≤ N < K) y aplicando la operación XOR como X = X X O N . Si no es posible, devuelve -1.

Ejemplos:

Entrada: X = 7, Y = 1, K = 5 
Salida: 2
Explicación:  Dado que en binario, X = 7 -> 111, Y = 1 -> 001,  
y dado que K = 5, N puede estar en el rango [1 , 4].
Ahora es necesario cambiar 2 bits en X para que sea igual a Y. 
Por lo tanto, los posibles valores de N pueden ser 6 (110), 4 (100), 2 (010)

• No podemos elegir 6 porque no está en el rango [1, 4]
• Elegiremos 4, haciendo X como X XOR 4 = 111 XOR 100 = 011
• Ahora nuevamente elegiremos 2, haciendo X como 011 XOR 010 = 001, que es lo mismo que Y.

Por lo tanto, se necesitan 2 operaciones para convertir X en Y. 

Entrada: X = 3, Y = 4, K = 10
Salida: 1

Planteamiento: Para resolver el problema siga las siguientes observaciones:

Sea V el XOR de X e Y. Ahora, queremos obtener V realizando XOR de la menor cantidad de elementos posible, no más de N.  
Disminuya el valor de K en 1 para que no seleccionemos N = K para realizar XOR.
Observamos los siguientes tres casos:

• si V = 0: Entonces necesitamos operaciones cero porque V=0 significa X⊕Y=0, lo que implica que X ya es igual a Y.
   
• si V < K: Entonces solo necesitamos 1 operación porque V < K implica que siempre es posible encontrar un número N menor que igual a K
  que en XOR con X dará Y. 
   
• Si log ₂ (V) = log ₂ (K): En la primera operación podemos cambiar solo el bit más significativo,  
  y en la segunda operación podemos cambiar todos los bits menos que el más significativo.
  Por lo tanto 2 operaciones. 

De lo contrario, no es posible hacer que X sea igual a Y haciendo XOR. Esto sucede en el caso de que el bit más grande de V sea mayor que el bit más grande de K, lo que significa que no podemos crear este bit más grande de ninguna manera. Por lo tanto imprimimos -1.

Siga los pasos dados para resolver el problema:

• Disminuya K en 1 para evitar seleccionar N = K para XOR.
• Almacene el XOR de X e Y en una variable (digamos V ).
• Ahora, encuentre el número mínimo de operaciones requeridas según las condiciones anteriores.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number of steps
int equalByXOR(int X, int Y, int K)
{
    // Decreasing K by 1 to avoid
    // selecting N == K for XORing
    K--;
 
    // Ctr variable to count the number of
    // operations required
    int ctr = 0;
 
    // V be the XOR of X and Y
    int V = X ^ Y;
 
    // Cases as discussed above in approach
    // 3 cases if possible
    if (V == 0) {
        ctr = 0;
    }
    else if (V <= K) {
        ctr = 1;
    }
    else if (K != 0 && __lg(V) == __lg(K)) {
        ctr = 2;
    }
    else {
 
        // If not possible
        ctr = -1;
    }
 
    // Return the minimum number of operations
    return ctr;
}
 
// Driver code
int main()
{
    int X = 7, Y = 1, K = 5;
 
    // Function call
    cout << equalByXOR(X, Y, K);
    return 0;
}

// Java code to implement the approach
import java.util.*;
 
class GFG{
 
  // Function to find the minimum number of steps
  static int equalByXOR(int X, int Y, int K)
  {
    // Decreasing K by 1 to avoid
    // selecting N == K for XORing
    K--;
 
    // Ctr variable to count the number of
    // operations required
    int ctr = 0;
 
    // V be the XOR of X and Y
    int V = X ^ Y;
 
    // Cases as discussed above in approach
    // 3 cases if possible
    if (V == 0) {
      ctr = 0;
    }
    else if (V <= K) {
      ctr = 1;
    }
    else if (K != 0 && Integer.highestOneBit(V) == Integer.highestOneBit(K)) {
      ctr = 2;
    }
    else {
 
      // If not possible
      ctr = -1;
    }
 
    // Return the minimum number of operations
    return ctr;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int X = 7, Y = 1, K = 5;
 
    // Function call
    System.out.print(equalByXOR(X, Y, K));
  }
}
 
// This code contributed by shikhasingrajput

# Python code to implement the approach
import math
 
# Function to find the minimum number of steps
 
 
def equalByXOR(X, Y, K):
    # Decreasing K by 1 to avoid
    # selecting N == K for XORing
    K -= 1
    # Ctr variable to count the number of
    # operations required
    ctr = 0
    # V be the XOR of X and Y
    V = X ^ Y
    # Cases as discussed above in approach
    # 3 cases if possible
    if V == 0:
        ctr = 0
 
    elif V <= K:
        ctr = 1
 
    elif K != 0 and int(math.log(V)) == int(math.log(K)):
        ctr = 2
 
    else:
        # If not possible
        ctr = -1
 
    # Return the minimum number of operations
    return ctr
 
 
# Driver code
if __name__ == "__main__":
    X = 7
    Y = 1
    K = 5
    # Function call
    print(equalByXOR(X, Y, K))
 
# This code is contributed by Rohit Pradhan

2

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