Работа с M-событиями среди N

Ответ 1

Вы делаете 64 суммы, по одному для каждого бита, для каждой из сумм, которые вы вычисляете sum 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-разрядные целые числа не переполняются.

Ответ 2

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

Мы можем обобщить метод xor для работы с произвольными m и n. Сначала нам нужно выбрать базу 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'ed base b на ожидаемое число. Мы можем просто вычислить я ^^ (m% b) для я = 0..b-1, а затем посмотреть, какое значение у нас есть в s для каждой цифры в результате.

Этот алгоритм является O (N). Для каждого числа в списке у нас есть постоянное количество операций, потому что у нас не более 64 цифр. Возвращение в конце в худшем случае O (N) для больших b. Мы можем сделать этот последний шаг в постоянном пространстве, вычислив я ^^ (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]. Мы генерируем таблицу я ^^ 2 для каждой цифры i, а затем выполняем обратный поиск.

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

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

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

Ответ 3

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

Ответ 4

Здесь решение, которое имеет такое же время работы, как eBusiness (которое я считаю фактически 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;
}

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

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

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

• т
• п
• 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)

Ответ 8

Уступка - это как процесс поиска статистики 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-го порядка.