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

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

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

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

Читать дальше ->

https://habrahabr.ru/post/349996/