Operaciones Bitwise XOR mínimas para hacer que dos elementos de array sean iguales

Posted on by Rudeus Greyrat

Dada una array arr[] de enteros de tamaño N y un entero K. Se puede realizar la operación Bitwise XOR entre cualquier elemento de array y K cualquier número de veces. La tarea es imprimir el número mínimo de tales operaciones requeridas para hacer que dos elementos de la array sean iguales. Si no es posible hacer que dos elementos de la array sean iguales después de realizar la operación mencionada anteriormente, imprima -1.
Ejemplos: 
 

Entrada: arr[] = {1, 9, 4, 3}, K = 3 
Salida: -1 
Explicación: No es posible hacer que dos elementos sean iguales
Entrada: arr[] = {13, 13, 21, 15}, K = 13 
Salida: 0 
Explicación: Ya existen dos elementos iguales

Enfoque: La observación clave es que si es posible hacer la array deseada, la respuesta será 0, 1 o 2. Nunca excederá 2. 
 

Porque, si (x ^ k) = y 
entonces, realizar (y ^ k) dará x nuevamente 
 

  1. La respuesta será 0 , si ya hay elementos iguales en la array.
  2. Para que la respuesta sea 1 , crearemos una nueva array b[] que contiene b[i] = (a[i] ^ K) , 
    ahora, para cada a[i] comprobaremos si hay algún índice j tal que i != j y a[i] = b[j] .
    Si es así, entonces la respuesta será 1 .
  3. Para que la respuesta sea 2 , buscaremos un índice i en la nueva array b[] , si hay algún índice j tal que i != j y b[i] = b[j] . 
    Si es así, entonces la respuesta será 2 .
  4. Si alguna de las condiciones anteriores no se cumple, la respuesta será -1 .

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// minimum operations required
int minOperations(int a[], int n, int K)
{
    unordered_map<int, bool> map;
    for (int i = 0; i < n; i++) {
 
        // Check if the initial array
        // already contains an equal pair
        if (map[a[i]])
            return 0;
        map[a[i]] = true;
    }
 
    // Create new array with XOR operations
    int b[n];
    for (int i = 0; i < n; i++)
        b[i] = a[i] ^ K;
 
    // Clear the map
    map.clear();
 
    // Check if the solution
    // is a single operation
    for (int i = 0; i < n; i++) {
 
        // If Bitwise XOR operation between
        // 'k' and a[i] gives
        // a number other than a[i]
        if (a[i] != b[i])
            map[b[i]] = true;
    }
 
    // Check if any of the a[i]
    // gets equal to any other element
    // of the array after the operation
    for (int i = 0; i < n; i++)
 
        // Single operation
        // will be enough
        if (map[a[i]])
            return 1;
 
    // Clear the map
    map.clear();
 
    // Check if the solution
    // is two operations
    for (int i = 0; i < n; i++) {
 
        // Check if the array 'b'
        // contains duplicates
        if (map[b[i]])
            return 2;
 
        map[b[i]] = true;
    }
 
    // Otherwise it is impossible to
    // create such an array with
    // Bitwise XOR operations
    return -1;
}
 
// Driver code
int main()
{
 
    int K = 3;
    int a[] = { 1, 9, 4, 3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // Function call to compute the result
    cout << minOperations(a, n, K);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.HashMap;
 
class GFG
{
    // Function to return the count of
    // minimum operations required
    static int minOperations(int[] a, int n, int k)
    {
        HashMap<Integer,
                Boolean> map = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
 
            // Check if the initial array
            // already contains an equal pair
            if (map.containsKey(a[i]) &&
                map.get(a[i]))
                return 0;
            map.put(a[i], true);
        }
 
        // Create new array with XOR operations
        int[] b = new int[n];
        for (int i = 0; i < n; i++)
            b[i] = a[i] ^ k;
 
        // Clear the map
        map.clear();
 
        // Check if the solution
        // is a single operation
        for (int i = 0; i < n; i++)
        {
 
            // If Bitwise XOR operation between
            // 'k' and a[i] gives
            // a number other than a[i]
            if (a[i] != b[i])
                map.put(b[i], true);
        }
 
        // Check if any of the a[i]
        // gets equal to any other element
        // of the array after the operation
        for (int i = 0; i < n; i++)
         
            // Single operation
            // will be enough
            if (map.containsKey(a[i]) &&
                map.get(a[i]))
                return 1;
 
        // Clear the map
        map.clear();
 
        // Check if the solution
        // is two operations
        for (int i = 0; i < n; i++)
        {
 
            // Check if the array 'b'
            // contains duplicates
            if (map.containsKey(b[i]) &&
                map.get(b[i]))
                return 2;
 
            map.put(b[i], true);
        }
 
        // Otherwise it is impossible to
        // create such an array with
        // Bitwise XOR operations
        return -1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int K = 3;
        int[] a = { 1, 9, 4, 3 };
        int n = a.length;
        System.out.println(minOperations(a, n, K));
    }
}
 
// This code is contributed by
// Vivek Kumar Singh

Python3

# Python3 implementation of the approach
 
# Function to return the count of
# minimum operations required
def minOperations(a, n, K) :
 
    map = dict.fromkeys(a, False);
    for i in range(n) :
 
        # Check if the initial array
        # already contains an equal pair
        if (map[a[i]]) :
            return 0;
        map[a[i]] = True;
 
    # Create new array with XOR operations
    b = [0] * n;
    for i in range(n) :
        b[i] = a[i] ^ K;
 
    # Clear the map
    map.clear();
 
    # Check if the solution
    # is a single operation
    for i in range(n) :
 
        # If Bitwise XOR operation between
        # 'k' and a[i] gives
        # a number other than a[i]
        if (a[i] != b[i]) :
            map[b[i]] = True;
     
    # Check if any of the a[i]
    # gets equal to any other element
    # of the array after the operation
    for i in range(n) :
 
        # Single operation
        # will be enough
        if a[i] in map :
            return 1;
 
    # Clear the map
    map.clear();
 
    # Check if the solution
    # is two operations
    for i in range(n) :
         
        # Check if the array 'b'
        # contains duplicates
        if b[i] in map :
            return 2;
 
        map[b[i]] = True;
 
    # Otherwise it is impossible to
    # create such an array with
    # Bitwise XOR operations
    return -1;
 
# Driver code
if __name__ == "__main__" :
 
    K = 3;
    a = [ 1, 9, 4, 3 ];
    n = len(a);
 
    # Function call to compute the result
    print(minOperations(a, n, K));
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
    // Function to return the count of
    // minimum operations required
    public static int minOperations(int[] a,
                                    int n, int K)
    {
 
        Dictionary<int, Boolean> map =
                new Dictionary<int, Boolean>();
 
        for (int i = 0; i < n; i++)
        {
 
            // Check if the initial array
            // already contains an equal pair
            if (map.ContainsKey(a[i]))
                return 0;
 
            map.Add(a[i], true);
        }
 
        // Create new array with XOR operations
        int[] b = new int[n];
        for (int i = 0; i < n; i++)
            b[i] = a[i] ^ K;
 
        // Clear the map
        map.Clear();
 
        // Check if the solution
        // is a single operation
        for (int i = 0; i < n; i++)
        {
 
            // If Bitwise OR operation between
            // 'k' and a[i] gives
            // a number other than a[i]
            if (a[i] != b[i])
                map.Add(b[i], true);
        }
 
        // Check if any of the a[i]
        // gets equal to any other element
        // of the array after the operation
        for (int i = 0; i < n; i++)
        {
 
            // Single operation
            // will be enough
            if (map.ContainsKey(a[i]))
                return 1;
        }
 
        // Clear the map
        map.Clear();
 
        // Check if the solution
        // is two operations
        for (int i = 0; i < n; i++)
        {
 
            // Check if the array 'b'
            // contains duplicates
            if (map.ContainsKey(b[i]))
                return 2;
            map.Add(b[i], true);
        }
 
        // Otherwise it is impossible to
        // create such an array with
        // Bitwise OR operations
        return -1;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int K = 3;
        int[] a = { 1, 9, 4, 3 };
        int n = a.Length;
        Console.WriteLine(minOperations(a, n, K));
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
 
// Javascript implementation of the approach
 
// Function to return the count of
// minimum operations required
function minOperations(a, n, K)
{
    var map = new Map();
    for (var i = 0; i < n; i++) {
 
        // Check if the initial array
        // already contains an equal pair
        if (map[a[i]])
            return 0;
        map[a[i]] = true;
    }
 
    // Create new array with XOR operations
    var b = Array(n);
    for (var i = 0; i < n; i++)
        b[i] = a[i] ^ K;
 
    // Clear the map
    map = new Map();
 
    // Check if the solution
    // is a single operation
    for (var i = 0; i < n; i++) {
 
        // If Bitwise XOR operation between
        // 'k' and a[i] gives
        // a number other than a[i]
        if (a[i] != b[i])
            map[b[i]] = true;
    }
 
    // Check if any of the a[i]
    // gets equal to any other element
    // of the array after the operation
    for (var i = 0; i < n; i++)
 
        // Single operation
        // will be enough
        if (map[a[i]])
            return 1;
 
    // Clear the map
    map = new Map();
 
    // Check if the solution
    // is two operations
    for (var i = 0; i < n; i++) {
 
        // Check if the array 'b'
        // contains duplicates
        if (map[b[i]])
            return 2;
 
        map[b[i]] = true;
    }
 
    // Otherwise it is impossible to
    // create such an array with
    // Bitwise XOR operations
    return -1;
}
 
// Driver code
var K = 3;
var a = [ 1, 9, 4, 3 ];
var n = a.length;
// Function call to compute the result
document.write( minOperations(a, n, K));
 
</script>   
Producción: 

-1

 

Publicación traducida automáticamente

Artículo escrito por gp6 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *