Znaleźć brakującą liczbę w sekwencji

Question

Dostałem listę liczb całkowitych n, a te liczby całkowite są w zakresie od 1 do n. Nie ma żadnych duplikatów na liście.Ale jedna z liczb całkowitych nie ma na liście.Musię znaleźć brakującą liczbę całkowitą.

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. 

Jednak powyższa metoda zakończy się niepowodzeniem, jeśli suma liczb przekroczy maksymalną dozwoloną liczbę całkowitą.

Więc szukał drugiego rozwiązania i znalazłem sposób jak następuje:

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. 

Jak działa ta metoda .. Jak jest XOR R1 i R2 wyszukuje brakujące całkowitą w powyższym przypadku ?

Answer 1

Aby odpowiedzieć na to pytanie, trzeba tylko pamiętać, że

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

i natychmiast wynika, że ​​

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

Aby udowodnić pierwszą nieruchomość, wystarczy napisać w dół tabeli XOR prawdzie

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

Tabela prawdy w skrócie: jeśli oba bity są takie same, wynikiem XOR jest fałsz, prawda o termicznie.

W przypadku niepowiązanej uwagi ta właściwość XOR czyni ją dobrą kandydatką do prostych (ale nie trywialnych) form szyfrowania.

Answer 2

Przede wszystkim możesz sprawić, by oryginalna metoda działała nawet w przypadku przekroczenia liczby całkowitej (tak długo, jak n pasuje do int).

Jeśli chodzi o metodę XOR, należy zauważyć, że R1 xor M == R2 (gdzie M jest brakującym numerem). Z tego wynika, że ​​R1 xor M xor R2 == 0, a zatem M == R1 xor R2.

Answer 3

W XOR działa, ponieważ za każdym razem ty XOR nieco z 1 flip, i za każdym razem XOR trochę z 0 pozostaje taka sama. Tak więc wynik XOR zapisania wszystkich danych zapisz brakujący numer daje "negatywne" wrażenie XOR wszystkich liczb. XOR Te dwa elementy przywracają utracony numer.

Answer 4

Spójrzmy na XOR bitu niskiego rzędu (LOB), aby zachować prostotę. Niech x będzie brakującą liczbą całkowitą.

Każda liczba całkowita na liście ma wartość 1 lub zero LOB wartości R1 (LOB (R1)).

Każda liczba całkowita z zakresu ma wartość 1 lub zero dla LOB (R2).

Teraz przypuśćmy, że LOB (R1) == LOB (R2). Ponieważ R2 == R2 XOR x, może się to zdarzyć tylko wtedy, gdy LOB (x) == 0 == LOB (R1) XOR LOB (R2). (1 xor 1 = 0, 0 xor 0 = 0)

Lub przypuść (LOB (R1) == LOB (R2) To może się zdarzyć tylko, jeśli LOB (x) == 1 == LOB (R1) XOR LOB (R2) (1 xor 0 = 1, 0 xor 1 = 1).

Ale to, co działa dla bitu niskiego rzędu, działa dla nich wszystkich, ponieważ XOR jest obliczane niezależnie, krok po kroku.