Trovare il numero mancante nella sequenza

Question

Mi è stata assegnata una lista di n numeri interi e questi numeri interi sono compresi nell'intervallo tra 1 e n. Non ci sono duplicati nell'elenco. Ma manca uno degli interi nell'elenco. Devo trovare il numero intero mancante.

Example: If n=8 
I/P [7,2,6,5,3,1,8] 
O/P 4 

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
     total = n*(n+1)/2 
And then Subtract all the numbers from sum. 

Ma il metodo sopra non funzionerà se la somma dei numeri supera il massimo consentito.

così ho cercato per una seconda soluzione e ho trovato un metodo come segue:?

1) XOR all the elements present in arr[], let the result of XOR be R1. 
2) XOR all numbers from 1 to n, let XOR be R2. 
3) XOR of R1 and R2 gives the missing number. 

come è questo metodo di lavoro .. Come è lo XOR di R1 e R2 trova il numero intero mancante nel caso di cui sopra ?

Answer 1

Per rispondere alla tua domanda, è sufficiente ricordare che

A XOR B = C => C XOR A = B 

e segue subito che

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR (PATIAL SUM) = (MISSING ELEMNT) 

Per dimostrare la prima proprietà, basta annotare il tavolo XOR verità:

A B | A XOR B 
0 0 | 0 
0 1 | 1 
1 0 | 1 
1 1 | 0 

Tabella di verità in breve: se entrambi i bit sono uguali, il risultato di XOR è falso, vero o therwise.

Su una nota non correlata, questa proprietà di XOR lo rende un buon candidato per forme di crittografia semplici (ma non banali).

Answer 2

Prima di tutto, è possibile rendere il metodo originale funzionante anche in presenza di overflow di numeri interi (purché n si adatti a un int).

Per quanto riguarda il metodo XOR, osservare che R1 xor M == R2 (dove M è il numero mancante). Da ciò segue che R1 xor M xor R2 == 0 e quindi M == R1 xor R2.

Answer 3

I XOR opere, perché ogni volta che si XOR un po 'con 1 si ribalta, e ogni volta che si XOR un po' con 0 rimane lo stesso. Quindi il risultato di in tutti i dati che salvano il numero mancante ti dà l'impressione "negativa" di XOR in tutti i numeri. XOR questi due insieme ripristina il numero perso.

Answer 4

Diamo un'occhiata allo XOR del bit di ordine basso (LOB) per semplificare le cose. Sia x il numero mancante.

Ogni numero intero contribuisce a 1 o a zero il LOB di R1 (LOB (R1)).

Ogni numero intero nell'intervallo contribuisce a 1 o a zero al LOB (R2).

Ora supponiamo LOB (R1) == LOB (R2). Poiché R2 == R2 XOR x, ciò può avvenire solo se LOB (x) == 0 == LOB (R1) XOR LOB (R2). (1 xor 1 = 0, 0 xor 0 = 0)

O supponiamo (LOB (R1) == LOB (R2). Ciò può accadere solo se LOB (x) == 1 == LOB (R1) XOR LOB (R2) (1 xor 0 = 1, 0 xor 1 = 1)

Ma ciò che funziona per il bit di ordine basso funziona per tutti, perché XOR è calcolato indipendentemente, bit per bit.