Поиск числа, отсутствующего в последовательности

Question

Мне присвоен список из n целых чисел, и эти целые числа находятся в диапазоне от 1 до n. В списке нет дубликатов. Но в списке отсутствует один из целых чисел. Мне нужно найти недостающее целое число.

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. 

Но вышеприведенный метод не сработает, если сумма чисел выходит за пределы максимально допустимого целого числа.

Так я искал второго раствора, и я нашел метод следующим образом:

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. 

Как этот метод работает .. Как это исключающее из R1 и R2 находит недостающее число в указанном выше случае ?

Answer 1

Чтобы ответить на ваш вопрос, вы просто должны помнить, что

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

и сразу следует, что

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

Чтобы доказать первое свойство, просто запишите XOR таблицей истинности:

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

Строка истины: если оба бита одинаковы, результат XOR является ложным, true o therwise.

В отношении несвязанной ноты это свойство XOR делает его хорошим кандидатом для простых (но не тривиальных) форм шифрования.

Answer 2

Прежде всего, вы можете сделать свой оригинальный метод работы даже при наличии целочисленного переполнения (до тех пор, пока n подходит для int).

Что касается метода XOR, обратите внимание, что R1 xor M == R2 (где M - это недостающее число). Из этого следует, что R1 xor M xor R2 == 0 и, следовательно, M == R1 xor R2.

Answer 3

В XOR работает, потому что каждый раз, когда вы XOR немного с 1 вы переверните его, и каждый раз, когда вы XOR немного с 0 он остается тем же самым. Таким образом, результат XOR всех данных, сохраняющих недостающее число, дает вам «отрицательное» впечатление от XOR всех номеров. XOR Эти два вместе восстанавливают ваш потерянный номер.

Answer 4

Давайте просто взглянем на XOR младшего разряда (LOB), чтобы все было просто. Пусть x - недостающее целое число.

Каждое целое число в списке вносит 1 или ноль LOB R1 (LOB (R1)).

Каждое целое число в диапазоне вносит 1 или 0 в LOB (R2).

Теперь предположим, что LOB (R1) == LOB (R2). Поскольку R2 == R2 XOR x, это может произойти только в том случае, если LOB (x) == 0 == LOB (R1) XOR LOB (R2). (1 xor 1 = 0, 0 xor 0 = 0)

Или предположим (LOB (R1) == LOB (R2). Это может произойти только в том случае, если LOB (x) == 1 == LOB (R1) XOR LOB (R2) (1 xor 0 = 1, 0 xor 1 = 1)

Но то, что работает для младшего разряда, работает для всех из них, поскольку XOR вычисляется независимо, по частям.