L'utilizzo dell'operatore XOR per la ricerca di elementi duplicati in un array ha esito negativo in molti casi

Question

Mi sono imbattuto in un post How to find a duplicate element in an array of shuffled consecutive integers? ma in seguito mi sono reso conto che questo non funziona per molti input.

Per esempio:
arr[] = {601,602,603,604,605,605,606,607}

#include <stdio.h> 
int main() 
{ 
int arr[] = {2,3,4,5,5,7}; 
int i, dupe = 0; 
for (i = 0; i < 6; i++) { 
    dupe = dupe^a[i]^i; 
} 
printf ("%d\n", dupe); 
return 0; 
} 

Come posso modificare il codice in modo che l'elemento duplicato può essere trovato per tutti i casi?

Answer 1

Da domanda iniziale:

Supponiamo di avere una matrice di 1001 interi. Gli interi sono in ordine casuale, ma sai che ognuno degli interi è compreso tra 1 e 1000 (inclusi). Inoltre, ogni numero appare solo una volta nell'array, ad eccezione di un numero, che si verifica due volte.

Si dice in sostanza, che l'algoritmo funziona solo quando si dispone di numeri interi consecutivi, iniziando con 1, per finire con alcuni N.

Se si desidera modificarlo per caso più generale, si deve fare Seguente:

Trova minimo e massimo nell'array. Quindi calcolare l'output previsto (xo tutti gli interi tra minimo e massimo). Quindi calcola xor di tutti gli elementi nella matrice. Quindi segui queste due cose e ottieni un risultato.

Answer 2

Ecco il codice mostrato nella domanda originale, che è diverso dalla vostra implementazione. È stato modificato in modo da utilizzare una variabile locale invece che l'ultimo membro della matrice, che fa la differenza:

for (int i = 1; i < 1001; i++) 
{ 
    array[i] = array[i]^array[i-1]^i; 
} 

printf("Answer : %d\n", array[1000]); 

Answer 3

Un'istruzione XOR ha la proprietà che 'a' XOR 'a' sarà sempre 0, cioè si annulla, quindi, se si sa che l'elenco ha solo un duplicato e che l'intervallo è da x a y , 601 a 607 nel tuo caso, è possibile mantenere l'xor di tutti gli elementi da x a y in una variabile, e quindi xor questa variabile con tutti gli elementi che hai nell'array. Dal momento che ci sarà un solo elemento che verrà duplicato, non verrà annullato a causa dell'operazione xor e questa sarà la tua risposta.

void main() 
{ 
    int a[8]={601,602,603,604,605,605,606,607}; 
    int k,i,j=601; 

    for(i=602;i<=607;i++) 
    { 
     j=j^i; 
    } 

    for(k=0;k<8;k++) 
    { 
     j=j^a[k]; 
    } 

    printf("%d",j); 
} 

Questo codice fornirà l'output 605, come desiderato!

Answer 4

//There i have created the program to find out the duplicate element in array. Please edit if there are required some changes. 
int main() 
{ 
    int arr[] = {601,602,603,604,605,605,606,607}; 
    //int arr[] = {601,601,604,602,605,606,607}; 
    int n= sizeof(arr)/sizeof(arr[0]); 

    for (int i = 0; i < n; i++) 
    { 
     for (int j = i+1; j < n; j++) 
     { 
      int res = arr[i]^arr[j]; 

      if (res == 0) 
      { 
       std::cout<< "Repeated Element in array = "<<arr[i]<<std::endl; 
      } 
     } 
    } 
    return 0; 
} 

// oppure è possibile utilizzare HashTable e funzione di hash quando si entra lo stesso
valore nella tabella di hash che il tempo si può fare se il suo conteggio maggiore di
un valore in particolare indice di HashTable poi si posso dire che ci sono valori ripetuti nell'array.