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

Пусть у нас есть массив положительных чисел, в котором все числа, кроме трех, встречаются по 2 раза, а эти три числа отличны от всех остальных и встречается каждое ровно по одному разу. Нужно найти эти три числа. Числа помещаются в 32-битный целочисленный тип.

Решение

Сделаем xor всех чисел, обозначим это число через x. Очевидно, что в итоге мы получим xor искомых трех чисел, так как остальные попарно сократятся (xor с сами собой — это ноль, а xor с нулем — это само число).

Рассмотрим побитовое представление числа x. Очевидно, что найдется хотя бы один такой бит, в котором одно из трех чисел отличается от двух других (иначе эти три числа были бы равными). Будем перебирать биты этого числа в некотором порядке. Пусть i-й бит числа равен 1. Тогда возможны два варианта: либо у одного из трех искомых чисел в этом бите 1, а у других 0, либо у всех 1.

В 1-м случае мы сможем выделить одно из трех чисел. Сделаем xor всех чисел массива у которых в i-м бите также 1, обозначим это число через y. Очевидно, что числа не входящие в искомые три числа сократятся, то есть мы получим xor тех чисел, которые входят в наши три числа, и у которых при этом в i-м бите 1. Если x = y, то реализовался второй случай, иначе первый случай.

В случае если i-й бит числа x равен 0, поступаем полностью аналогично. В этом случае у нас будут варианты: либо у всех трех чисел i-й бит 0, либо у одного числа i-й бит 0, а у двух других 1. Аналогично находим xor всех чисел у которых в i-м бите 0 и если мы получили число не равное x, то мы выделили одно из трех чисел.

Так как хотя бы в одном бите одно из трех чисел будет отличаться от остальных двух, то мы точно сможем выделить одно из чисел. Далее находим xor двух оставшихся чисел, для этого xor’им x с выделенным числом. Задача свелась к такой же, только в ней вместо трех чисел — два, каждое встречается по одному разу, выделенное ранее третье число больше нигде не будем учитывать. Одно из двух чисел выделяется аналогично, при этом не нужно перебирать биты, которые мы уже перебрали, когда выделяли первое число, так как оставшиеся два числа в них совпадают, иначе бы мы выделили одно из них.

Со свойствами битовых операций можете ознакомиться в отдельной статье.