Имея дело с M вхождений среди N

Question

Вопрос, который мне дали на собеседовании.Я был близок к решению, но, к сожалению, не смог его решить.

Предположим, у нас есть последовательность, которая содержит N чисел типа long.И мы точно знаем, что среди этой последовательности каждое число встречается ровно n раз, за ​​исключением одного числа, которое встречается ровно m раз( 0 <<strong> м <<strong> n ).Как найти это число с помощью O (N) операций и O (1) дополнительной памяти?

Для простейшего случая (когда n = 2 и m = 1 ) все, что нам нужно сделать, это просто выполнить накопительное xor на каждом номере в последовательности.Результат будет равен желаемому числу.Но я застреваю при попытке разобраться с произвольными м и n .

Буду признателен за реальныйРешение C ++.

---

РЕДАКТИРОВАТЬ: Нам известны фактические значения m и n a priori.

Пример. Мы знаем, что n = 3 и m = 2. Последовательность( N = 8 ) равно

5 11 5 2 11 5 2 11

И правильный ответ 2 в данном конкретном случае, потому чтоэто происходит только дважды.

Answer 1

Вы делаете 64 суммы, по одной на каждый бит, для каждой из сумм, которые вы вычисляете, сумма mod n, это вычисление возвращает m для каждого бита, который должен быть установлен в результате, и 0 для каждого бита, который не должен быть установлен .

Пример:
n = 3, m = 2. list = [5 11 5 2 11 5 2 11]

              5  11   5   2  11   5   2  11
sum of bit 0: 1 + 1 + 1 + 0 + 1 + 1 + 0 + 1 = 6   6 % 3 = 0
sum of bit 1: 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1 = 5   5 % 3 = 2
sum of bit 2: 1 + 0 + 1 + 0 + 0 + 1 + 0 + 0 = 3   3 % 3 = 0
sum of bit 3: 0 + 1 + 0 + 0 + 1 + 0 + 0 + 1 = 3   3 % 3 = 0

Таким образом, устанавливается только бит 1, что означает, что результат равен 2.

Оптимизация реализации:
(Уловки и соображения, которые также полезны для реальных проблем)
Стоит отметить, что при итерации по массиву скорость выполнения в некоторой степени будет ограничена доступом к памяти, если требуется выполнить несколько операций с каждым элементом, обычно быстрее всего выполнить их все по одному элементу за раз, таким образом, Процессору нужно загрузить каждый элемент из памяти только один раз. Интересное сообщение в блоге о памяти и кеше.

Можно суммировать несколько битов в одно целое число, вместо применения 64 разных битовых масок, чтобы получить каждый бит самостоятельно, например, можно использовать только 4 битовые маски, каждая из которых извлекает 16 бит с 3 битами между ними, как до тех пор, пока не произойдет переполнения, нормальная операция сложения будет работать точно так же, как если бы она работала с 16 4-битными целыми числами, поэтому этот метод будет работать для 15 чисел. После того, как 15 чисел были обработаны таким образом, результаты должны быть добавлены в хранилище, способное содержать большие целые числа (может быть 8 64-разрядных целых, каждое из которых содержит 8 8-разрядных целых чисел, они, конечно, должны быть в свою очередь очищены в большие целые числа и т. Д.). ).
В результате вместо того, чтобы каждое значение выполняло 64 битовых маски, 63 битовых смещения и 64 добавления, нужно всего лишь 4 битовых маски, 3 битовых смещения и 4 добавления, плюс для каждых 15 значений 8 битовых масок, 4 битовых смещения и 8 сложений, плюс для каждых 255 значений 16 битовых масок, 8 битовых смещений и 16 дополнений и т. Д.

Визуализация:
(Суммирование 4x4-битных целых чисел с использованием 16-битных целых)

1000 1000 1000 1000 +
1000 0000 0000 1000 +
0000 0000 0000 1000 +
1000 1000 0000 0000 +
1000 0000 1000 0000 +
0000 0000 1000 1000 =
0010 0100 1100 0010

Результат одинаков, если вы считаете, что это 4 столбца 4-битных целых или 1 столбец 16-битного целого, это верно только до тех пор, пока 4-битные целые числа не переполняются.

Answer 2

edit) Хорошо, этот метод не такой надежный, как я изначально думал.Решение eBusiness намного проще и работает правильно для таких случаев, как n = 4, m = 2.

. Мы можем обобщить метод xor для работы с произвольными m и n * 1008.*.Сначала нам нужно выбрать базу b , такую, что gcd (n, b) = b и gcd (m, b) .Поскольку нечетные n / четные m пары удовлетворяют этому для базы 2, стандартный двоичный xor работает для этих пар.

Сначала мы определяем (a ^^n) в значении (a ^ a ^ ... ^ a) для na , с обобщенным xor основания b .Например, со стандартным двоичным xor, a ^^ 2 = 0 .

Нам нужно определить наш обобщенный xor.Свойства, которые мы желаем, в основном такие же, как и сложение (коммутативность, ассоциативность), и нам нужно a ^^ b = 0 .Очевидное решение: (x ^ y) = (x + y)% b для каждой цифры в базовом представлении b (убедитесь, что это работает, и то же самое, что двоичный xorдля базы 2).Затем мы просто применяем это ко всем числам в последовательности и в итоге получаем result = s ^^ (m% b) , где s - специальное число.
Наконец, нам нужно вернутьсянаш «xor» базовый номер b до ожидаемого числа.Мы можем просто вычислить i ^^ (m% b) для i = 0..b-1 , а затем посмотреть, какое значение мы имеем в s для каждой цифры в результат .

Этот алгоритм будет O (N).Для каждого числа в списке у нас есть постоянное число операций, потому что у нас есть максимум 64 цифры.Возврат в конце - в худшем случае O (N) для большого b.Мы можем сделать этот последний шаг в постоянном пространстве, вычислив i ^^ (m% b) для всех i для каждой цифры (опять же, у нас есть постоянное количество цифр).

---

Пример:

n = 3, m = 2. list = [5 11 5 2 11 5 2 11]

Сначала мы выбираембаза b .Очевидно, нам нужно выбрать базу 3.

Таблица xor для справки:

  0|1|2
0|0|1|2
1|1|2|0
2|2|0|1

Вычисление:

  5     11      5      2     11      5      2     11
0^0=0. 0^1=1. 1^0=1. 1^0=1. 1^1=2. 2^0=2. 2^0=2. 2^1=0.
0^1=1. 1^0=1. 1^1=2. 2^0=2. 2^0=2. 2^1=0. 0^0=0. 0^0=0.
0^2=2. 2^2=1. 1^2=0. 0^2=2. 2^2=1. 1^2=0. 0^2=2. 2^2=1.

m % b = 2.

Таким образом, мы имеем s ^^ 2 = [001].Мы генерируем таблицу из i ^^ 2 для каждой цифры i, а затем делаем обратный поиск.

   i | 0 | 1 | 2 |
i^^2 | 0 | 2 | 1 |

0 -> 0
0 -> 0
1 -> 2

Наконец, мы конвертируем наш результат обратно в двоичное / десятичное число.[002] = 2

Answer 3

Вот решение, которое имеет то же время работы, что и электронный бизнес (которое я считаю фактически O (N log N)), но действительно использует O (1) слов памяти.Предполагается, что m не кратно n.Он также предполагает две вспомогательные функции, которые считают количество элементов строго выше и ниже их аргументов.

int divider = 0;

for (int i = 63; i >= 0; i--) {
  divider |= 1 << i;
  int a = countAbove(divider);
  int b = countBelow(divider);
  if (a % n == 0 && b % n == 0) return divider;
  else if (a % n == 0) divider ^= 1 << i;
}

Answer 4

Ваш простейший случай может быть более общим, вы можете использовать ту же методику, которую вы описали для нечетного числа m и четного числа n .

Answer 5

• Если у вас есть однозначный хэш на множестве целых чисел от 0 до (N / n) + 1, то вы можете решить его за N итераций + N / n итераций с использованием N памяти. Однако нет однозначного отображения

• Если нет ограничений на память, это просто должно быть константой, вы можете определить массив размером с домен long, чтобы затем вы могли решить проблему в 2N с постоянным гигантским использованием памяти. Для каждого x в N вы просто добавляете в BIGARRY [x], затем цикл, хотя BIGARRY ищет m. Это ужасно и нереализуемо, но отвечает требованиям, и большинство вопросов для интервью в любом случае являются мысленными экспериментами.

Answer 6

Раствор похож на процесс поиска статистики k-го порядка

by dividing the sequence into 2 sub-seqs
(calculate the size of sub-seqs during the procedure)
while (sizeof(sub-seq) mod n != 0)
  do the same porcess on this sub-seq(dividing)

O (N) операций, таких как поиск статистики k-го порядка.

Answer 7

Я считаю, что вы не можете сделать это, используя только O (1) дополнительное пространство.

Вот мое оправдание: вам дано:

• m
• n
• x_1 x_2 .. x_N

Поскольку среди значений x_i есть дубликаты, давайте определим U как набор уникальных значений.Все элементы в U появляются n раз, и один из них появляется m раз в серии x_i.Обозначим менее часто появляющийся элемент как u_0, а U_1 - множество U - {u_0}.

Пусть S - сумма всех x_i.S можно записать в виде:

sum(x_i) = n * sum(U_1) + m * u_0 = n * sum(U) + (m - n) * u_0

Решение этой проблемы эквивалентно нахождению суммы уникальных элементов в серии, и вы не можете сделать это в O (1) дополнительном пространстве, потому что вам нужномассив или хеш-таблица со связанными элементами - на самом деле это пространство O (N)

Answer 8

Если список отсортирован, то это становится довольно простым, так как вам просто нужно проверить каждую партию по очереди, чтобы узнать, равна ли она длине m.

Если список не отсортирован, то я не думаю, что это возможно с O (1) дополнительной памятью.