Looks like "insanity" got the best of both of you and you participated despite having exams the next day :)

У меня вообще неприятные ощущения от этой задачи. Это даже не боян, это... Давать такое — моветон. Т.е. задача весьма очевидным способом сводится к "есть ли в массиве число, которое встречается больше N/2 раз, какое это число и сколько раз встречается?", а дальше уже полнейший боян. Эта задача есть на большинстве китайских архивов, есть на тимусе, и, что еще хуже, она очень популярна на собеседованиях в Google и Facebook (ну и подозреваю, что не только там), и есть в большинстве популярных статей и сборников "какие задачи надо уметь решать для собеседования". А эти статьи АСМщики читают, вероятно, чаще чем Кормена)) Я бы сравнил ее с задачей, где просят в массиве найти единственное число, у которого нету пары. И точно так же считаю плохой идеей давать такое на раунд. Ну ладно, это так, мое субъективное мнение, проехали.

А стандартное решение — за О(N) времени и О(1) памяти, идея в нем простая. Заведем стек, рассматривая очередное число — будем добавлять его в стек, если стек пустой или на верхушке стека число, совпадающее с нашим, или же будем удалять верхнее число стека (не добавляя наше) в противоположном случае. Далее можно заметить, что если в этом стеке что-то есть, то это одно и то же число, а не несколько разных, и перейти от стека к паре "значение — сколько раз в стеке", и это дает нам О(1) памяти.

Ключевое наблюдение — в массиве может быть только одно число, у которого больше N/2 повторений, и если такое число есть, то в конце выполнения алгоритма в стеке будет именно это число. Действительно, каждому "недостающему" вхождению этого числа в стэк можно сопоставить какое-то другое число, которым мы "сожгли" наше число (если в какой-то момент оно было в стеке) или которое мы "сожгли" нашим числом (если в момент его рассмотрения в стеке было что-то другое, и мы его так и не добавили). А таких "других чисел" будет меньше, чем вхождений нашего числа (потому что его, по условию, больше половины), следовательно, оно точно должно остаться в стеке хоть в одном экземпляре. А как мы уже знаем, в стеке в каждый момент времени может быть только одно число, а не несколько различных.

Так что первым проходом моделируем этой стек и определяем, что в нем будет после выполнения алгоритма. Это и будет наше "подозрительное" число. Вторым проходом считаем, сколько на самом деле раз встречается подозрительное число, и отсюда получаем ответ.

Пусть всего есть N человек. Ключевой момент — все "плохие" пары будут содержать один и тот же элемент (доказывается от противного). Предполагаем, что этот элемент встречается чаще чем N / 2 раз — тогда его можно найти за один проход (выкидываем попарно различные, оставшийся в конце X — наш). Ещё за один проход находим сколько именно раз встретился X — пусть встретился Y раз; если Y <= N / 2, то ответ N / 2, иначе N — Y.

А еще без стека можно, в два прохода. Памяти больше, чем O(1), но зато до такого решения, лично мне, было проще додуматься.
Первый проход, находим самый частый 20-битный префикс:

S[1 << 20];
S[a[i] >> 12] += 1

Второй проход, находим самое частое число:

D[1 << 12];
if ((a[i] >> 12) == MostFreqPrefix) { D[a[i] & 0xFFF] += 1; }

Максимальное число в D[] — количество вхождений самого частого элемента, если он встречается больше, чем N/2 раз.
Проходит.