programa en C ++ para encontrar dos números únicos de una matriz

programa en C ++ para encontrar dos números únicos de una matriz: Aquí, vamos a aprender a encontrar dos números únicos de una matriz dada usando operadores de bits ?

Descripción:

solución para encontrar los dos números únicos a partir del conjunto de los números que se produjo dos veces aceptar los números únicos

Planteamiento del problema:

Escribir un programa en C ++ que acepte la entrada matriz a partir de usuario y encontrar los dos número único que se ha producido sólo una vez en conjunto .

Ejemplo:

    Input: 
10
1 1 2 3 3 4 4 5 6 6
Output:
2 5

Explicación:

Este problema puede resolverse utilizando el concepto de XOR bit a bit, AND bit a bit, y el enmascaramiento de bits.

XOR bit a bit:

XOR bit a bit (^) realiza dos patrones de bits de igual longitud. Si ambos bits en la posición comparación de los patrones de bits son 0 o 1, el bit en el patrón de bits resultante es 0, de lo contrario 1.

Ejemplo:

    A = 5 = 0101, B = 3 = 0011
A ^ B = 0101 ^ 0011 = 0110 = 6
Special Property of XOR:
A^A =0
A^0 = A

AND bit a bit

AND bit a bit (^) toma dos patrones de bits de igual longitud. La salida de AND bit a bit es 1 si los bits correspondientes de dos operandos es 1. Si una de bit de un operando es 0, el resultado de bit correspondiente se evalúa a 0.

Ejemplo:

    A = 5 = 0101, B = 3 = 0011
A & B = 0101 & 0011 = 0001 = 1

class el problema actual:

  1. En primer lugar tomamos XOR de todos los elementos de la matriz.
  2. supongamos que tenemos: 1,1,2,3,3,4,4,5,6,6
  3. Al tomar XOR de todos los elementos, esto eliminará los elementos duplicados como A ^ A = 0
    Entonces conseguimos: 2 ^ 5 del resultado anterior
  4. el resultado de 2 ^ 5 sin duda tendrá al menos un conjunto de bits, para encontrar el conjunto más a la derecha bit hacemos res y 1 y hacer un recuento de tomar la comunicación de la posición actual. Si obtenemos un valor distinto de cero res y 1 Esa es la posición que queremos conseguir, For el bucle, de lo contrario el desplazamiento a la derecha res y el incremento del recuento.
  5. hacer una máscara usando 1 & lt; & lt; recuento , y tomar y uno por uno con todos los elementos, elementos resultantes un resultado no cero de máscara y arr [i] , tomar XOR de ellos.
  6. resultante XOR dará lugar a firstNo .
  7. Ahora class SecondNo , tomar XOR de firstNo con res iniciales . es decir, firstNo ^ firstNo ^ secondNo .

Algoritmo:

  1. Set res = 0 y encontrar su XOR con todos los demás elementos de la matriz.
  2. Ahora res = firstNo ^ secondNo .
  3. Obtener posición de bit más a la derecha del conjunto res . usando la función findRightMostBit
  4. Set bitPos = posición de bit conjunto más a la derecha.
  5. establecer una máscara con una estructura de conjunto de bits en la posición bitPos , utilizando 1 & lt; & lt; bitPos .
  6. Conjunto firstNo = 0
  7. For i=0 to size of array
    If mask & arr[i] != 0
    firstNo = firstNo ^ arr[i]
    //End of if
    //End of loop

  8. Set secondNo = firstNo ^ res .
  9. Imprimir firstNo y secondNo .

Programa:

#include<bits/stdc++.h>
using namespace std;
int findRightMostBit(int x) {
int i = 0;
while (x > 0) {
if(x&1){
return i;
}
x>>1;
i++;
}
return i;
}
void findUnique(int arr[], int size) {
int res = 0;
for (int i = 0; i < size; ++i) {
res = res ^ arr[i];
}
int bitPos = findRightMostBit(res);
int mask = (1 << bitPos);
int firstNo=0;
for (int i = 0; i < size; ++i)
{
if ((mask & arr[i]) != 0) {
firstNo = firstNo ^ arr[i];
}
}
int secondNo = firstNo^ res;
cout<<"Two Unique Numbers : "<<firstNo<<" , "<<secondNo;
}
int main() {
int n;
cout<<"Enter size of array : ";
cin>>n;
int arr[n];
cout<<"Enter elements of array : n";
for (int i = 0; i < n; ++i)
{
cin>>arr[i];
}
findUnique(arr, n);
return 0;
}

salida

Enter size of array : 10
Enter elements of array :
1 1 2 3 3 4 4 5 6 6
Two Unique Numbers : 5 , 2


Deja un comentario

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