Опять же, откидываем все решения через сортировку и мапы - они не самые эффективные. Хоть и более "программистские" чтоли.
Вернемся к решению к ксором.
Вот мы проксорили первым проходом весь массив. Получили на выходе ксор наших одиноких элементов. И что теперь делать? Как из этого значения получить оригинальные элементы?
А никак! Но мы можем использовать эту информацию для нахождения нужных элементов. Для определенности представим, что наши искомые числа обозначаются, как
a и b, a ^ b - полученный результат после первого прохода.Так как для одинаковых чисел xor будет давать ноль, то для разных чисел он будет давать какой-то ненулевой результат. Ненулевой - значит в бинарном представлении это значение будет иметь хотя бы единичку в каком-то из битов. Именно в этом бите N и будут различаться наши числа. А раз мы знаем, в каком бите различаются числа, то во время второго прохода мы можем отдельно ксорить числа с выставленным N битом и с невыставленным. По условию, только два числа непарные, а все остальные - парные. Пары чисел будут попадать в одну из групп и при ксоре будут занулять друг друга. Тогда у нас будут две суммы по модулю 2, которые и будут равняться нашим искомым a и b.
Битовые манипуляции - вещь, поэтому очень круто знать разные приемы с их использованием. Иногда это может значительно облегчить вам жизнь.
Solve your problems. Stay cool.
