Задача про результаты голосования

Прочитав заголовок недавнего поста ^[1], я быстро приготовил себе вкусный чай и уселся поудобнее, надеясь с пользойинтересом провести следующие несколько часов. Каково же было моё расстройство, когда в условии я увидел заезженную тему про xor c небольшой вариацией (не в укор автору, я говорю про себя, и, неверняка, есть много людей, которые ещё не знакомы с этим типом задач). Да, её было интересно решить, но за 5 минут чай даже не успел остыть. И тогда я подумал, что могут быть и другие люди, которым было бы интересно часок-другой занять себя. Поэтому вот вам другая задача.

В городе N прошли выборы, где один из кандидатов победил с перевесом в 50% или более голосов. Результаты голосования опубликованы в виде списка голосов от каждого жителя. Список состоит из целых чисел — номеров кандидатов, каждое число помещается в машинном слове. Требуется за один проход и 1KB памяти выяснить номер победившего кандидата.

В отличие от других постов подобного типа, я решил не публиковать решение, потому что задача мне показалась уникальной, и я бы не хотел, чтобы армия HR-ов или seniour lead software engineering interview architects разнесла её по всему свету, как это случилось с множеством других логических задач. Я однозначно против таких задач на собеседованиях. Я убедительно прошу в комментариях озвучивать только подходы к решению, но не выкладвать его полностью. Если вы хотите проверить свою гипотезу — напишите мне. Удовольствие от решения гарантирую 100% или верну вам деньги. Если два или более человека напишут, что это известная задача (или дадут отсылку), то решение я опубликую.

Всем весёлых выходных!

Автор: mbait

Источник ^[2]