Ci sono numeri da 1 a N presenti in un elenco e un numero aggiuntivo che è stato incluso per errore. Quindi, in totale ci sono numeri N + 1. Supponiamo che il numero intero più grande che la lingua può gestire sia N. Qual è l'algoritmo più veloce per trovare la cifra di ripetizione?
Nota: questo non è un problema di compiti a casa.
Vorrei xor tutti i numeri e xor quello con quello che avrebbe dovuto essere lo xor della lista completa. (Che xor dipende da N e non è difficile da capire.)
Funziona perché xor ha le seguenti proprietà:
a xor b = b xor a
(a xor b) xor c = a xor (b xor c)
a xor 0 = a
Ancora meglio, lo fa senza mai cambiare quanti bit hai nella tua rappresentazione. E xor sembra essere una delle operazioni più veloci in un computer.
Quindi il risultato di questo calcolo è lo stesso che otterresti se abbiassi ciascun numero nell'elenco con una copia di se stesso, li facessi xori tutti insieme, quindi il numero extra inserito da mistke. Ma questo si trasforma in 0 xored con se stesso un sacco di volte poi xored con il numero extra. Che diventa tutto solo il numero in più.
Leggi altre domande sui tag algorithms