Найти повторяющиеся и пропущенные числа в заданном массиве

Question

Для данного массива A, содержащего числа от 1 до N, я хочу найти пару чисел (x, y), которая повторяется и отсутствует. Пример A = [1, 3, 3], тогда x = 3 и y = 2.

Хотя я знаю, что эту проблему можно решить, взяв упомянутый здесь подход xor https://stackoverflow.com/a/5767648/5031518. Мне не удается понять последнюю часть решения, где значения x и y извлекаются из x ^ y путем разделения массива на основе установленного бита.

Было бы полезно, если бы кто-то мог объяснить мне, почему xor двух списков приводит к значениям x и y соответственно.

Answer 1

На первом этапе вы вычисляете xor значений во всем диапазоне 1..N и в своем списке

1  2  3 .. x .. N  
1  2  3 ..   .. N  y

xor всех парных элементов дает 0, поэтому результат равен p = x xor y

Значение p ненулевое, но какие биты установлены?Они различаются по x и y.

Таким образом, мы можем найти любой 1-бит из p, назвать его mask и выполнить ту же процедуру для значений 1..N и вашего списка, выбирая только значенияэтот бит установлен

for all v in 1..N and in list:   
   if ((v & mask) == mask):
       newxor ^= v

В конце концов, newxor содержит или x или y (все остальные элементы, участвующие здесь, являются парными), и мы можем найти другой элемент с помощью

 xy = p ^ newxor

Примечание: мы не можем различить, какой элемент был повторен, а что пропущен, просто получить пару из них.

Для вашего примера

p = 1^2^3^1^3^3 = 1 = 001 binary

повторение процедуры с маской 001b включает только нечетные числа

 newxor = (1 xor 3) xor (1 xor 3 xor 3) = 3

, а остальное число

 3 xor 1 = 2

Например, (1,2,2) мы получаем такие же p

p = 1^2^3^1^2^2 = 1 = 001 binary

итот же newxor = 3 и то же значение покоя xy=2