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

Мне предоставлен список из 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.

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

Ответы

Ответ 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 равен false, в противном случае - true.

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Каждое целое число в диапазоне вносит 1 или ноль в 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 вычисляется независимо, по-бит.