Task 18_1. Вывести 2 непарных элемента в числовом массиве

Task 18_1. Вывести 2 непарных элемента в числовом массиве

UniLecs

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

Идея: если просто сделать xor всех чисел в массиве, понятно что результатом будет first^second - xor двух непарных чисел.

Давайте сделаем xor всех чисел, у которых в бите i допустим 1. При xor'е всех чисел у которых i-й бит равен 1 некоторые пары одинаковых чисел попадут в "один набор", другие в другой.

В любом случае xor парных чисел будет равен нулю, но при этом в 1й блок попадет лишь одно из непарных чисел. В итоге мы получим first или second.  Так как у нас есть значение first^second, то мы получим и второе число.

Реализация:

реализация на JS

https://gist.github.com/unilecs/d312f1714d94b0010121aa791a4108e4



Report Page