Dada una array arr de longitud N de números distintos y un entero X , la tarea es encontrar la cantidad mínima de elementos que deben agregarse en la array de modo que los elementos de la array se puedan agrupar en pares donde el XOR bit a bit de cada par es igual a X.
Ejemplos:
Entrada: N = 3, arr[] = {1, 2, 3}, X = 1
Salida: 1
Explicación: Si agregamos 0 a la array, la array se convierte en {1, 2, 3, 0}.
Esta array se puede dividir como (1, 0), (2, 3), donde XOR de cada par es 1.Entrada: N = 5, arr[] = {1, 4, 5, 6, 7}, X = 7
Salida: 3
Explicación: Si sumamos (2, 0, 3) a la array, se convierte en [1, 4 , 5, 6, 7, 2, 0, 3].
Esta array se puede dividir como (1, 6), (4, 3), (5, 2), (7, 0), con XOR de cada par como 7.
Enfoque: el problema se puede resolver utilizando las propiedades del operador Bitwise XOR :
De acuerdo con la pregunta, supongamos que cada par de Array tiene un valor XOR bit a bit como X, es decir
array[i] ⊕ array[j] = X
Dado que la declaración anterior es verdadera, por lo tanto, la declaración siguiente también será verdadera
array[i] ⊕ X = array[j]
Con base en la relación anterior, podemos resolver este problema de la siguiente manera:
- Descubra los pares existentes en Array con valor XOR bit a bit como X, e ignórelos ya que no contribuirán a la solución.
- De los elementos restantes, el XOR bit a bit de cada elemento con X será el elemento que se agregará en el Array para satisfacer la restricción dada.
- Por lo tanto, el recuento del elemento restante será el recuento requerido de inserciones necesarias en el Array para dividirlo en pares con XOR bit a bit como X.
Siga los pasos mencionados a continuación para implementar la idea:
- Cree una array de frecuencias para almacenar la frecuencia de los elementos de la array.
- Inserte el primer elemento de la array en la estructura de datos hash.
- Ejecute un bucle de i = 1 a N-1 :
- Compruebe si A[i] ⊕ X ya se encuentra en la array o no.
- Si no lo encuentra, inserte el elemento actual en la estructura de datos hash.
- De lo contrario, disminuya la frecuencia de ese elemento.
- Devuelve el número total de elementos que aún no ha formado un par.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find out minimum number of
// element required to make array good
int minNumbersRequired(int N, int arr[], int X)
{
// Variable to store the minimum number of
// elements required
int count = 0;
// Map to store the frequency
unordered_map<int, int> freq;
freq[arr[0]]++;
for (int i = 1; i < N; i++) {
// If arr[i]^X is found,
// then remove one occurrence
// of both the elements from the map
// as their bitwise XOR is already X
if (freq[arr[i] ^ X] > 0) {
freq[arr[i] ^ X]--;
}
else
freq[arr[i]]++;
}
// Count the number of elements remaining
// in the Array as the required answer
for (auto it = freq.begin(); it != freq.end(); it++)
count += it->second;
// Return the minimised count of insertions
return count;
}
// Driver Code
int main()
{
int N = 5;
int arr[] = { 1, 4, 5, 6, 7 };
int X = 7;
// Function call
cout << minNumbersRequired(N, arr, X);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find out minimum number of
// element required to make array good
public static int minNumbersRequired(int N, int arr[],
int X)
{
// Variable to store the minimum number of
// elements required
int count = 0;
// Map to store the frequency
HashMap<Integer, Integer> freq = new HashMap<>();
freq.put(arr[0], 1);
for (int i = 1; i < N; i++) {
// If arr[i]^X is found,
// then remove one occurrence
// of both the elements from the map
// as their bitwise XOR is already X
if (freq.get(arr[i] ^ X) == null)
freq.put(arr[i] ^ X, 1);
else if (freq.get(arr[i] ^ X) > 0) {
freq.put(arr[i] ^ X,
freq.get(arr[i] ^ X) - 1);
}
else
freq.put(arr[i] ^ X, 1);
}
// Count the number of elements remaining
// in the Array as the required answer
for (Map.Entry<Integer, Integer> it :
freq.entrySet())
count += it.getValue();
// Return the minimised count of insertions
return count;
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int arr[] = { 1, 4, 5, 6, 7 };
int X = 7;
// Function call
System.out.print(minNumbersRequired(N, arr, X));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code to implement the approach
# Function to find out minimum number of
# element required to make array good
def minNumbersRequired(N, arr, X):
# Variable to store the minimum number of
# elements required
count = 0
# Map to store the frequency
freq = {}
freq[arr[0]] = 1
for i in range(1,N):
# If arr[i]^X is found,
# then remove one occurrence
# of both the elements from the map
# as their bitwise XOR is already X
if ((arr[i] ^ X) in freq and freq[arr[i] ^ X] > 0):
freq[arr[i] ^ X] -= 1
else:
if (arr[i] in freq):
freq[arr[i]] += 1
else:
freq[arr[i]] = 1
# Count the number of elements remaining
# in the Array as the required answer
for it in freq:
count += freq[it]
# Return the minimised count of insertions
return count
# Driver Code
N = 5
arr = [1, 4, 5, 6, 7]
X = 7
# Function call
print(minNumbersRequired(N, arr, X))
# This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find out minimum number of
// element required to make array good
public static int minNumbersRequired(int N, int[] arr,
int X)
{
// Variable to store the minimum number of
// elements required
int count = 0;
// Map to store the frequency
Dictionary <int, int> freq = new Dictionary < int, int > ();
freq[arr[0]] = 1;
for (int i = 1; i < N; i++) {
// If arr[i]^X is found,
// then remove one occurrence
// of both the elements from the map
// as their bitwise XOR is already X
if (!freq.ContainsKey(arr[i] ^ X))
freq[arr[i] ^ X] = 1;
else if (freq[arr[i] ^ X] > 0) {
freq[arr[i] ^ X] -= 1;
}
else
freq[arr[i] ^ X] = 1;
}
// Count the number of elements remaining
// in the Array as the required answer
foreach(KeyValuePair<int, int> it in freq)
count += it.Value;
// Return the minimised count of insertions
return count;
}
public static void Main(string[] args)
{
int N = 5;
int[] arr = { 1, 4, 5, 6, 7 };
int X = 7;
// Function call
Console.WriteLine(minNumbersRequired(N, arr, X));
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code to implement the approach
// Function to find out minimum number of
// element required to make array good
const minNumbersRequired = (N, arr, X) => {
// Variable to store the minimum number of
// elements required
let count = 0;
// Map to store the frequency
let freq = {};
freq[arr[0]] = 1;
for (let i = 1; i < N; i++) {
// If arr[i]^X is found,
// then remove one occurrence
// of both the elements from the map
// as their bitwise XOR is already X
if ((arr[i] ^ X) in freq && freq[arr[i] ^ X] > 0) {
freq[arr[i] ^ X]--;
}
else {
if (arr[i] in freq)
freq[arr[i]]++;
else freq[arr[i]] = 1;
}
}
// Count the number of elements remaining
// in the Array as the required answer
for (let it in freq)
count += freq[it];
// Return the minimised count of insertions
return count;
}
// Driver Code
let N = 5;
let arr = [1, 4, 5, 6, 7];
let X = 7;
// Function call
document.write(minNumbersRequired(N, arr, X));
// This code is contributed by rakeshsahni
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)