Task 18_1. Вывести 2 непарных элемента в числовом массиве
UniLecsЗадача: дан массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза, кроме двух элементов. Найти числа без пары.
Идея: если просто сделать xor всех чисел в массиве, понятно что результатом будет first^second - xor двух непарных чисел.
Давайте сделаем xor всех чисел, у которых в бите i допустим 1. При xor'е всех чисел у которых i-й бит равен 1 некоторые пары одинаковых чисел попадут в "один набор", другие в другой.
В любом случае xor парных чисел будет равен нулю, но при этом в 1й блок попадет лишь одно из непарных чисел. В итоге мы получим first или second. Так как у нас есть значение first^second, то мы получим и второе число.
Реализация:
https://gist.github.com/unilecs/d312f1714d94b0010121aa791a4108e4