Trova numero intero non presente due volte in un array

Question

Sto cercando di risolvere questo problema: In un array intero tutti i numeri si verificano esattamente due volte, ad eccezione di un numero singolo che si verifica esattamente una volta.

Una soluzione semplice consiste nell'ordinare l'array e quindi verificare la non ripetizione. Ma sto cercando una soluzione migliore che abbia la complessità temporale di O (n).

Answer 1

È possibile utilizzare l'operazione "xor" sull'intero array. Ogni coppia di numeri si cancellerà a vicenda, lasciandovi il valore ricercato.

int get_orphan(int const * a, int len) 
{ 
    int value = 0; 
    for (int i = 0; i < len; ++i) 
     value ^= a[i]; 

    // `value` now contains the number that occurred odd number of times. 
    // Retrieve its index in the array. 
    for (int i = 0; i < len; ++i) 
    { 
     if (a[i] == value) 
      return i; 
    } 

    return -1; 
}