Die fehlende Nummer in der Sequenz finden

Question

Ich habe eine Liste von n ganzen Zahlen gegeben und diese ganzen Zahlen sind im Bereich von 1 bis n. Es gibt keine Duplikate in der Liste. Aber eine der ganzen Zahlen fehlt in der Liste. Ich muss die fehlende ganze Zahl finden.

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. 

Die obige Methode schlägt jedoch fehl, wenn die Summe der Zahlen die maximal zulässige Ganzzahl überschreitet.

Also suchte ich nach einer zweiten Lösung und fand ich eine Methode wie folgt:?

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. 

Wie wird diese Methode funktioniert .. Wie das XOR von R1 und R2 findet die fehlende ganze Zahl im obigen Fall ?

Answer 1

Ihre Frage zu beantworten, müssen Sie nur noch, dass

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

erinnern

und es folgt sofort, dass

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

die erste Eigenschaft Um zu beweisen, notieren Sie sich nur die Tabelle XOR Wahrheit:

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

Wahrheitstabelle kurz: Wenn beide Bits identisch sind, ist das Ergebnis von XOR falsch, wahr o darüber hinaus.

In einer nicht verwandten Anmerkung, diese Eigenschaft von XOR macht es zu einem netten Kandidaten für einfache (aber nicht triviale) Formen der Verschlüsselung.

Answer 2

Als Erstes können Sie Ihre ursprüngliche Methode auch bei Vorhandensein eines Ganzzahlüberlaufs arbeiten lassen (solange n in eine int passt).

Beachten Sie bei der XOR-Methode, dass R1 xor M == R2 (wobei M die fehlende Nummer ist). Daraus folgt, dass R1 xor M xor R2 == 0 und damit M == R1 xor R2.

Answer 3

Die XOR funktioniert, weil jedes Mal, wenn Sie XOR ein bisschen mit 1 Sie es drehen, und jedes Mal, wenn Sie XOR ein wenig mit 0 bleibt es gleich. Das Ergebnis von XOR alle Daten speichern die fehlende Zahl gibt Ihnen den "negativen" Eindruck von XOR alle Zahlen. XOR Diese beiden zusammen stellen Ihre verlorene Nummer wieder her.

Answer 4

Betrachten wir einfach das XOR des niederwertigen Bits (LOB), um die Dinge einfach zu halten. Sei x die fehlende ganze Zahl.

Jede ganze Zahl in der Liste trägt eine 1 oder eine Null zum LOB von R1 bei (LOB (R1)).

Jede ganze Zahl im Bereich trägt eine 1 oder eine Null zum LOB (R2) bei.

Angenommen, LOB (R1) == LOB (R2). Da R2 == R2 XOR x ist, kann dies nur passieren, wenn LOB (x) == 0 == LOB (R1) XOR LOB (R2). (1 x oder 1 = 0, 0 x oder 0 = 0)

Oder angenommen (LOB (R1) == LOB (R2). Dies kann nur passieren, wenn LOB (x) == 1 == LOB (R1) XOR LOB (R2) (1 x oder 0 = 1, 0 x oder 1 = 1)

Aber was für das Bit niedriger Ordnung funktioniert, funktioniert für alle, weil XOR unabhängig, Stück für Stück berechnet wird.