Двоично-троичная битовая магия

Существует классическая задача для собеседований, часто формулируемая следующим образом:

Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза, и только одно из чисел не имеет пары. Необходимо предложить алгоритм, который за минимальное число проходов по массиву определяет число, не имеющее пары.

Полагаю, никто не обидится, если я тут же приведу и решение задачи: уникальный элемент будет совпадать с $xor$-суммой всех элементов массива, вычисляемой за линейное время.

Предлагаю поразмыслить над другой вариацией данной задачи. Что, если все элементы, кроме искомого, будут присутствовать в массиве не парами, а тройками? Насколько при этом усложнится решение и останется ли оно линейным?

Читать дальше →
Двоично-троичная битовая магия
Source: habrahabr