Имея дело с M вхождений среди N
Вопрос, который мне дали на собеседовании. Я был близок к решению, но, к сожалению, не решил его.
Предположим, у нас есть последовательность, которая содержитN номера типаlong, И мы точно знаем, что среди этой последовательности каждое число встречается точноn раз за исключением одного числа, которое встречается точноm раз (0 < m < n). Как мы находим это число сНА) операции иO (1) дополнительная память?
Для самого простого случая (когдаn = 2 а такжеm = 1) все, что мы должны сделать, это просто выполнить накопительноеxor на каждом номере в последовательности. Результат будет равен желаемому числу. Но я застрял при попытке справиться с произвольнымm а такжеn.
Я был бы признателен за реальное решение C ++.
РЕДАКТИРОВАТЬ: Мы знаем фактические значенияm а такжеn априори.
Пример. Мы знаем этоn = 3 иm = 2. Последовательность (N = 8) является
5 11 5 2 11 5 2 11
И правильный ответ2 в данном конкретном случае, потому что это происходит только дважды.