Простой вопрос интервью усложнился: по номерам 1..100 найдите пропущенные числа, по которым точно k отсутствуют

Некоторое время назад у меня был интересный опыт собеседования. Вопрос начался очень просто:

Q1 : У нас есть пакет , содержащий номера 1, 2, 3..., 100. Каждый номер появляется ровно один раз, поэтому есть 100 номеров. Теперь один номер случайно выбирается из сумки. Найдите пропущенный номер.

Конечно, я слышал этот вопрос раньше, поэтому очень быстро ответил:

A1 : Ну, сумма чисел 1 + 2 + 3 + … + Nравна (N+1)(N/2)(см. Википедия: сумма арифметических рядов ). Ибо N = 100сумма есть 5050.

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

В этот момент я думал, что у меня все хорошо, но внезапно вопрос принял неожиданный оборот:

Q2 : Это правильно, но как бы вы это сделали, если ДВЕ номера не хватает?

Я никогда раньше не видел / не слышал / не рассматривал эту вариацию, поэтому запаниковал и не смог ответить на вопрос. Интервьюер настаивал на том, чтобы знать мой мыслительный процесс, поэтому я упомянул, что, возможно, мы можем получить больше информации, сравнивая с ожидаемым продуктом, или, возможно, сделав второй проход после сбора некоторой информации с первого прохода и т. Д., Но я действительно просто снимал в темноте, а не на самом деле иметь четкий путь к решению.

Интервьюер попытался меня ободрить, сказав, что наличие второго уравнения действительно является одним из способов решения проблемы. В этот момент я был немного расстроен (из-за того, что не знал ответа заранее) и спросил, является ли это общей (читай: «полезной») техникой программирования или это просто ответ с подвохом.

Ответ интервьюера удивил меня: вы можете обобщить технику, чтобы найти 3 пропущенных числа. Фактически, вы можете обобщить это, чтобы найти k пропущенных чисел.

Qk : Если в сумке нет ровно k чисел, как бы вы нашли это эффективно?

Это было несколько месяцев назад, и я до сих пор не могу понять, что это за техника. Очевидно , что это Ω(N)время нижней границы , так как мы должны сканировать все номера , по крайней мере , один раз, но интервьюер настаивает , что ВРЕМЯ и ПРОСТРАНСТВО сложность методы решения задачи (минус O(N)входном сканирование времени) определяются в к не N .

Так что вопрос здесь прост:

• Как бы вы решили Q2 ?
• Как бы вы решили Q3 ?
• Как бы вы решили Qk ?

Разъяснения

• Обычно есть N чисел от 1 .. N , а не только 1..100.
• Я не ищу очевидное основанное на множестве решение, например, используя набор битов , кодируя присутствие / отсутствие каждого числа значением назначенного бита, поэтому используя O(N)биты в дополнительном пространстве. Мы не можем позволить себе любое дополнительное пространство , пропорциональное N .
• Я также не ищу очевидного подхода первого порядка. Этот и основанный на множестве подходы заслуживают упоминания в интервью (они просты в реализации и в зависимости от N могут быть очень практичными). Я ищу решение Святого Грааля (которое может или не может быть практичным для реализации, но, тем не менее, имеет желаемые асимптотические характеристики).

Итак, еще раз, конечно, вы должны сканировать входные данные O(N), но вы можете захватить только небольшое количество информации (определяемой в терминах k, а не N ), а затем должны как-то найти k пропущенных чисел.

Вот краткое изложение ссылки Димитриса Андреу .

Запомните сумму i-й степени, где i = 1,2, .., k. Это сводит проблему к решению системы уравнений

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

Используя тождества Ньютона , зная, что b _i позволяет вычислить

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

с _к = а ₁ а ₂ ... a _k

Если развернуть многочлен (xa ₁ ) ... (xa _k ), коэффициенты будут точно c ₁ , ..., c _k - см . Формулы Виета . Поскольку каждый полиномиальный фактор однозначно (кольцо полиномов является евклидовой областью ), это означает, что a _i однозначно определены, с точностью до перестановки.

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

Однако, когда k изменяется, прямой подход к вычислению c ₁ , ..., c _k является чрезмерно дорогим, поскольку, например, c _k является произведением всех пропущенных чисел, величина n! / (Nk) !. Чтобы преодолеть это, выполните вычисления в поле Z _q , где q такое простое число, что n <= q <2n - оно существует по постулату Бертрана . Доказательство менять не нужно, поскольку формулы все еще выполняются, а факторизация полиномов по-прежнему уникальна. Вам также нужен алгоритм для факторизации по конечным полям, например алгоритм Берлекампа или Кантора-Цассенхауза .

Псевдокод высокого уровня для константы k:

• Вычислить i-й степени заданных чисел
• Вычтите, чтобы получить суммы i-й степени неизвестных чисел. Назовите суммы b _i .
• Используйте тождества Ньютона для вычисления коэффициентов из b _i ; называть их c _i . В основном, c ₁ = b ₁ ; c ₂ = (c _1, b ₁ - b ₂ ) / 2; см. Википедию для точных формул
• Фактор многочлена x ^k -c ₁ x ^k-1 + ... + c _k .
• Корнями многочлена являются нужные числа a ₁ , ..., a _k .

Для варьирования k найдите простое число n <= q <2n, используя, например, Миллера-Рабина, и выполните шаги с уменьшением всех чисел по модулю q.

РЕДАКТИРОВАТЬ: предыдущая версия этого ответа заявил, что вместо Z _q , где q является простым, можно использовать конечное поле характеристики 2 (q = 2 ^ (log n)). Это не так, поскольку формулы Ньютона требуют деления на числа до k.

Вы найдете это, прочитав пару страниц алгоритмов Muthukrishnan - Data Stream: Головоломка 1: Поиск пропущенных чисел . Он показывает именно то обобщение, которое вы ищете . Возможно, именно это прочитал ваш интервьюер и почему он задал эти вопросы.

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

Также смотрите прямой ответ sdcvvc , который также включает псевдокод (ура! Нет необходимости читать эти хитрые математические формулировки :)) (спасибо, отличная работа!).

Мы можем решить Q2, суммируя как сами числа, так и квадраты чисел.

Затем мы можем уменьшить проблему до

k1 + k2 = x
k1^2 + k2^2 = y

Где xи yкак далеко суммы ниже ожидаемых значений.

Подставляя дает нам:

(x-k2)^2 + k2^2 = y

Что мы можем затем решить, чтобы определить наши пропущенные числа.

Как указал @j_random_hacker, это очень похоже на поиск дубликатов в O (n) времени и O (1) пространстве , и адаптация моего ответа там тоже работает.

Предполагая, что «мешок» представлен массивом A[]размером 1 N - k, мы можем решить Qk во O(N)времени и O(k)дополнительном пространстве.

Во- первых, мы расширим наш массив с A[]помощью kэлементов, так что теперь размер N. Это O(k)дополнительное пространство. Затем мы запускаем следующий алгоритм псевдокода:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

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

Второй цикл переставляет расширенный массив, так что если элемент xприсутствует хотя бы один раз, то одна из этих записей будет в позицииA[x] .

Обратите внимание, что, хотя у него есть вложенный цикл, он все еще выполняется во O(N)времени - своп происходит только в том случае, если есть iтакой A[i] != i, и каждый своп устанавливает как минимум один элемент, такой A[i] == i, где это не было ранее. Это означает, что общее количество перестановок (и, следовательно, общее количество выполнений whileтела цикла) не более N-1.

Третий цикл печатает те индексы массива i, которые не заняты значением i- это означает, что, iдолжно быть, отсутствовал.

Я попросил 4-летнего ребенка решить эту проблему. Он отсортировал числа и затем сосчитал. Это требует пространства O (пол на кухне) и работает так же просто, как и многие шары.

Не уверен, что это наиболее эффективное решение, но я бы перебрал все записи и использовал набор битов, чтобы запомнить, какие числа установлены, а затем проверил наличие 0 битов.

Мне нравятся простые решения - и я даже считаю, что это может быть быстрее, чем вычисление суммы или суммы квадратов и т. Д.

Я не проверял математику, но подозреваю, что вычисления Σ(n^2)на одном и том же проходе, когда мы вычисляем Σ(n), предоставят достаточно информации для получения двух пропущенных чисел, Σ(n^3)а также, если их три, и так далее.

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

Мы можем проанализировать временную и пространственную сложность алгоритмов sdcvvc и Dimitris Andreou.

Место хранения:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Так l_j \in \Theta(j log n)

Общее количество использованного хранилища: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Используемое пространство: при условии, что вычисления a^jзанимают ceil(log_2 j)время, общее время:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Общее использованное время: \Theta(kn log n)

Если это время и пространство удовлетворительное, вы можете использовать простой рекурсивный алгоритм. Пусть b! I будет i-й записью в сумке, n числом чисел перед удалением и k количеством изъятий. В синтаксисе Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Используемое хранилище: O(k)для списка, O(log(n))для стека: O(k + log(n)) этот алгоритм более интуитивен, имеет ту же сложность времени и использует меньше места.

Подожди минуту. Поскольку вопрос установлен, в сумке есть 100 чисел. Независимо от того, насколько велико k, проблему можно решить за постоянное время, потому что вы можете использовать набор и удалять числа из набора в самое большее 100 - k итераций цикла. 100 постоянна. Набор оставшихся чисел - ваш ответ.

Если мы обобщим решение для чисел от 1 до N, ничего не изменится, за исключением того, что N не является константой, поэтому мы находимся в O (N - k) = O (N) времени. Например, если мы используем набор битов, мы устанавливаем биты в 1 за O (N), перебираем числа, устанавливая биты в 0 по мере продвижения (O (Nk) = O (N)), а затем есть ответ.

Мне кажется, что интервьюер спрашивал вас, как распечатать содержимое окончательного набора за O (k), а не O (N). Ясно, что с установленным битом вам нужно пройти через все N битов, чтобы определить, следует ли вам печатать число или нет. Однако, если вы измените способ реализации набора, вы можете распечатать числа за k итераций. Это делается путем помещения чисел в объект, который будет храниться как в хэш-наборе, так и в двусвязном списке. Когда вы удаляете объект из хеш-набора, вы также удаляете его из списка. Ответы останутся в списке, который теперь имеет длину k.

Чтобы решить вопрос о 2 (и 3) пропущенных числах, вы можете изменить его quickselect, который в среднем работает O(n)и использует постоянную память, если разбиение выполняется на месте.

1. Разбейте набор относительно случайного центра pна разделы l, которые содержат числа, меньшие, чем центр, и rкоторые содержат числа, большие, чем центр.

2. Определите, в каких разделах находятся 2 пропущенных числа, сравнив значение сводки с размером каждого раздела ( p - 1 - count(l) = count of missing numbers in lи n - count(r) - p = count of missing numbers in r)

3. a) Если в каждом разделе пропущено одно число, используйте подход разностей сумм, чтобы найти каждое пропущенное число.

   (1 + 2 + ... + (p-1)) - sum(l) = missing #1 а также ((p+1) + (p+2) ... + n) - sum(r) = missing #2

   б) если один раздел отсутствует как число и раздел пуст, то недостающие цифры либо (p-1,p-2)или в (p+1,p+2) зависимости от того, какой из разделов отсутствуют число.

   Если в одном разделе пропущены 2 числа, но он не пуст, вернитесь к этому разделу.

При наличии только 2 пропущенных чисел этот алгоритм всегда отбрасывает хотя бы один раздел, поэтому он сохраняет O(n)среднюю сложность быстрого выбора. Точно так же с 3 пропущенными числами этот алгоритм также отбрасывает по крайней мере один раздел с каждым проходом (потому что как с 2 пропущенными числами, самое большее только 1 раздел будет содержать несколько пропущенных чисел). Тем не менее, я не уверен, насколько снижается производительность, когда добавляется больше пропущенных чисел.

Вот реализация, которая не использует разделение на месте, поэтому этот пример не соответствует требованию к пространству, но он иллюстрирует шаги алгоритма:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

демонстрация

Вот решение, которое использует k бит дополнительной памяти, без каких-либо хитрых уловок и просто. Время выполнения O (n), дополнительное пространство O (k). Просто чтобы доказать, что это можно решить, не читая сначала о решении и не будучи гением:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Можете ли вы проверить, существует ли каждый номер? Если да, вы можете попробовать это:

S = сумма всех чисел в сумке (S <5050)
Z = сумма пропущенных чисел 5050 - S

если пропущенные числа, xа yзатем:

x = Z - y и
max (x) = Z - 1

Итак, вы проверяете диапазон от 1до max(x)и находите число

Может быть, этот алгоритм может работать на вопрос 1:

1. Предварительно вычислить xor первых 100 целых чисел (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
2. xor элементы, поскольку они продолжают поступать из входного потока (val1 = val1 ^ next_input)
3. окончательный ответ = val ^ val1

Или даже лучше:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Этот алгоритм может быть фактически расширен для двух пропущенных чисел. Первый шаг остается прежним. Когда мы вызываем GetValue с двумя пропущенными числами, результатом будет a1^a2два пропущенных числа. Допустим

val = a1^a2

Теперь, чтобы отсеять a1 и a2 от val, мы берем любой установленный бит в val. Допустим, ithбит установлен в val. Это означает, что a1 и a2 имеют разную четность в ithпозиции бита. Теперь мы делаем еще одну итерацию для исходного массива и сохраняем два значения xor. Один для чисел, у которых установлен i-й бит, а другой - без установленного i-го бита. Теперь у нас есть две группы чисел, и она гарантированно a1 and a2будет лежать в разных группах. Теперь повторите то же самое, что мы сделали для нахождения одного пропущенного элемента в каждом ведре.

Вы можете решить Q2, если у вас есть сумма обоих списков и произведение обоих списков.

(l1 - оригинал, l2 - модифицированный список)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Мы можем оптимизировать это, поскольку сумма арифметического ряда в n раз больше среднего первого и последнего членов:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Теперь мы знаем, что (если a и b - удаленные числа):

a + b = d
a * b = m

Таким образом, мы можем изменить:

a = s - b
b * (s - b) = m

И умножить:

-b^2 + s*b = m

И переставить так, чтобы правая сторона была равна нулю

-b^2 + s*b - m = 0

Тогда мы можем решить с помощью квадратной формулы:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Пример кода Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Я не знаю сложности функций sqrt, Reduce и Sum, поэтому я не могу решить сложность этого решения (если кто-то знает, пожалуйста, прокомментируйте ниже.)

Для Q2 это решение, которое немного более неэффективно, чем другие, но все еще имеет время выполнения O (N) и занимает пространство O (k).

Идея состоит в том, чтобы запустить оригинальный алгоритм два раза. В первом вы получите общее число, которое отсутствует, что дает вам верхнюю границу пропущенных чисел. Давайте назовем этот номер N. Вы знаете, что пропущенные два числа будут суммироваться до N, поэтому первое число может быть только в интервале, [1, floor((N-1)/2)]пока второе будет [floor(N/2)+1,N-1].

Таким образом, вы снова зацикливаетесь на всех числах, отбрасывая все числа, которые не включены в первый интервал. Те, которые, вы отслеживаете их сумму. Наконец, вы узнаете одно из двух пропущенных чисел и, в дополнение, второе.

У меня есть ощущение, что этот метод может быть обобщен, и, возможно, несколько запросов выполняются "параллельно" в течение одного прохода по входу, но я еще не выяснил, как.

Я думаю, что это можно сделать без каких-либо сложных математических уравнений и теорий. Ниже приведено предложение по решению проблемы сложности на месте и времени O (2n):

Предположения формы ввода:

Количество чисел в сумке = n

Количество пропущенных номеров = k

Числа в сумке представлены массивом длины n

Длина входного массива для алгоритма = n

Недостающие записи в массиве (числа, извлеченные из пакета) заменяются значением первого элемента в массиве.

Например. Изначально сумка выглядит как [2,9,3,7,8,6,4,5,1,10]. Если выбрано 4, значение 4 станет 2 (первый элемент массива). Таким образом, после того, как вынуть 4, сумка будет выглядеть как [2,9,3,7,8,6,2,5,1,10]

Ключ к этому решению состоит в том, чтобы пометить INDEX посещенного номера, отрицая значение в этом INDEX, когда массив пересекается.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

Существует общий способ обобщения потоковых алгоритмов, подобных этому. Идея состоит в том, чтобы использовать немного рандомизации, чтобы, как мы надеемся, «распределить» kэлементы по независимым подзадачам, где наш оригинальный алгоритм решает эту проблему для нас. Этот метод используется, среди прочего, при восстановлении разреженных сигналов.

• Сделайте массив aразмером u = k^2.
• Выберите любой универсальный хэш - функции , h : {1,...,n} -> {1,...,u}. (Как многократная смена )
• Для каждого iв 1, ..., nувеличенииa[h(i)] += i
• Для каждого числа xво входном потоке уменьшать a[h(x)] -= x.

Если все пропущенные числа были хэшированы в разные сегменты, ненулевые элементы массива теперь будут содержать пропущенные числа.

Вероятность того, что конкретная пара отправляется в одно и то же ведро, меньше, чем 1/uпо определению универсальной хеш-функции. Поскольку речь k^2/2идет о парах, мы имеем вероятность ошибки не более k^2/2/u=1/2. То есть мы добиваемся успеха с вероятностью не менее 50%, и если мы увеличиваем, uмы увеличиваем наши шансы.

Обратите внимание, что этот алгоритм занимает k^2 lognбиты пространства (нам нужно lognбитов на массив). Это соответствует пространству, требуемому для ответа @Dimitris Andreou (В частности, требование к пространству для полиномиальной факторизации, которая также бывает рандомизированной.) Этот алгоритм также имеет константу время на обновление, а не время kв случае сумм мощности.

Фактически, мы можем быть даже более эффективными, чем метод суммирования мощности, используя прием, описанный в комментариях.

Очень простое решение Q2, на которое я удивляюсь, никто уже не ответил. Используйте метод из Q1, чтобы найти сумму двух пропущенных чисел. Обозначим его через S, тогда одно из пропущенных чисел меньше, чем S / 2, а другое больше, чем S / 2 (дух). Суммируйте все числа от 1 до S / 2 и сравните его с результатом формулы (аналогично методу в Q1), чтобы найти меньшее из пропущенных чисел. Вычтите это из S, чтобы найти большее пропущенное число.

Очень хорошая проблема. Я бы пошел за использование разницы набора для Qk. Многие языки программирования даже поддерживают его, как в Ruby:

missing = (1..100).to_a - bag

Возможно, это не самое эффективное решение, но я бы использовал его в реальной жизни, если бы столкнулся с такой задачей в этом случае (известные границы, низкие границы). Если бы набор чисел был очень большим, я бы, конечно, рассмотрел более эффективный алгоритм, но до этого мне было бы достаточно простого решения.

Вы можете попробовать использовать фильтр Блума . Вставьте каждый номер в сумке в цвету, затем итерируйте полный набор 1-k, пока не сообщите о каждом не найденном. Это может не найти ответ во всех сценариях, но может быть достаточно хорошим решением.

Я бы использовал другой подход к этому вопросу и исследовал интервьюера для получения более подробной информации о более крупной проблеме, которую он пытается решить. В зависимости от проблемы и требований, окружающих ее, очевидное решение на основе множеств может быть правильным, а подход «генерировать список и выбирать через него» может и не быть.

Например, может случиться так, что интервьюер собирается отправлять nсообщения и ему нужно знать, kчто не привело к ответу, и ему нужно знать это за минимальное время после настенного времениn-k ответа. Давайте также скажем, что характер канала сообщений таков, что даже при работе на полную длину у вас есть достаточно времени для некоторой обработки между сообщениями без какого-либо влияния на время, необходимое для получения конечного результата после получения последнего ответа. Это время можно использовать для вставки некоторого идентифицирующего аспекта каждого отправленного сообщения в набор и удаления его по мере поступления каждого соответствующего ответа. Как только последний ответ получен, единственное, что нужно сделать, это удалить его идентификатор из набора, который в типичных реализациях принимаетO(log k+1), После этого набор содержит список kотсутствующих элементов, и дополнительная обработка не требуется.

Это, конечно, не самый быстрый подход для пакетной обработки предварительно сгенерированных пакетов чисел, потому что все работает O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Но он работает для любого значения k(даже если оно не известно заранее) и в приведенном выше примере он был применен таким образом, чтобы минимизировать самый критический интервал.

Вы можете мотивировать решение, думая об этом с точки зрения симметрии (группы, на языке математики). Независимо от порядка набора чисел, ответ должен быть одинаковым. Если вы собираетесь использовать kфункции для определения отсутствующих элементов, вам следует подумать о том, какие функции имеют это свойство: симметричное. Функция s_1(x) = x_1 + x_2 + ... + x_nявляется примером симметричной функции, но есть и другие, более высокой степени. В частности, рассмотрим элементарные симметричные функции . Элементарная симметричная функция степени 2 является s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_nсуммой всех произведений двух элементов. Аналогично для элементарных симметрических функций степени 3 и выше. Они явно симметричны. Кроме того, оказывается, что они являются строительными блоками для всех симметричных функций.

Вы можете построить элементарные симметричные функции по ходу, отметив это s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Дальнейшая мысль должна убедить вас в этом s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))и так далее, чтобы их можно было вычислить за один проход.

Как нам определить, какие элементы отсутствовали в массиве? Подумайте о полиноме (z-x_1)(z-x_2)...(z-x_n). Он оценивает, 0если вы введете любое из чисел x_i. Расширяя полином, вы получаете z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Здесь также появляются элементарные симметричные функции, что неудивительно, поскольку многочлен должен оставаться прежним, если мы применим любую перестановку к корням.

Таким образом, мы можем построить многочлен и попытаться разложить его, чтобы выяснить, какие числа не входят в набор, как уже упоминали другие.

Наконец, если нас беспокоит переполнение памяти большими числами (n-й симметричный многочлен будет порядка 100!), мы можем выполнить эти вычисления, mod pгде pпростое число больше 100. В этом случае мы оцениваем многочлен mod pи находим, что оно снова вычисляет чтобы , 0когда вход представляет собой число в наборе, и она вычисляется в ненулевое значение , когда вход числа , не в наборе. Однако, как уже отмечалось, для получения значений из полинома во времени , которое зависит от k, не N, мы должны фактор многочлен mod p.

Еще одним способом является использование остаточной фильтрации графов.

Предположим, у нас есть номера от 1 до 4, а 3 отсутствует. Бинарное представление следующее,

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

И я могу создать потоковую диаграмму, как показано ниже.

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

Обратите внимание, что потоковый граф содержит х узлов, а х - количество битов. А максимальное количество ребер равно (2 * х) -2.

Таким образом, для 32-разрядного целого числа потребуется O (32) пробел или O (1) пробел.

Теперь, если я уберу емкость для каждого числа, начиная с 1,2,4, то у меня останется остаточный график.

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

Наконец, я запустите цикл, как показано ниже,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Теперь результат resultсодержит числа, которые также не пропущены (ложное срабатывание). Но k <= (размер результата) <= n, когда kотсутствуют элементы.

Я пройду по данному списку в последний раз, чтобы отметить пропущенный результат или нет.

Таким образом, сложность времени будет O (n).

Наконец, можно уменьшить число ложноположительных (и пространство , необходимое), принимая узлы 00, 01, 11, 10вместо того , чтобы просто 0и 1.

Вам, вероятно, нужно уточнить, что означает O (k).

Вот тривиальное решение для произвольного k: для каждого v в вашем наборе чисел накапливайте сумму 2 ^ v. В конце, цикл i от 1 до N. Если сумма поразрядно ANDed с 2 ^ i равна нулю, то i отсутствует. (Или численно, если пол суммы, деленной на 2 ^ i четен. Или sum modulo 2^(i+1)) < 2^i.)

Легко, правда? O (N) время, O (1) память, и это поддерживает произвольное k.

За исключением того, что вы вычисляете огромные числа, которые на реальном компьютере требуют пространства O (N). Фактически это решение идентично битовому вектору.

Таким образом, вы можете быть умным и вычислить сумму и сумму квадратов и сумму кубов ... вплоть до суммы v ^ k, и сделать причудливую математику, чтобы извлечь результат. Но это тоже большие цифры, поэтому возникает вопрос: о какой абстрактной модели работы идет речь? Сколько места в O (1) пространстве, и сколько времени нужно, чтобы сложить числа любого размера вам нужно?

Вот решение, которое не полагается на сложную математику, как это делают ответы sdcvvc / Dimitris Andreou, не меняет входной массив, как это сделали caf и полковник Panic, и не использует набор огромных размеров, как Chris Lercher, JeremyP и многие другие сделали. По сути, я начал с идеи Свалорцена / Гилада Дойча для Q2, обобщил ее для общего случая Qk и реализовал в Java, чтобы доказать, что алгоритм работает.

Идея

Предположим, у нас есть произвольный интервал I, из которого мы знаем только то, что он содержит хотя бы одно из пропущенных чисел. После того, как один проход через входной массив, только глядя на цифры от I , можно получить как сумму S и величину Q недостающих чисел от I . Мы делаем это, просто уменьшая длину I каждый раз, когда мы встречаем число от I (для получения Q ), и уменьшая предварительно вычисленную сумму всех чисел в I на это число каждый раз (для получения S ).

Теперь мы смотрим на S и Q . Если Q = 1 , то это означает , что тогда я содержит только один из недостающих чисел, и это число явно S . Мы помечаем I как завершенный (в программе это называется «однозначным») и оставляем его для дальнейшего рассмотрения. С другой стороны, если Q> 1 , мы можем вычислить среднее A = S / Q недостающих чисел содержится в I . Поскольку все числа различны, по крайней мере , один из таких чисел строго меньше , чем А и по меньшей мере один строго больше , чем A . Теперь мы разобьем I в Ана два меньших интервала, каждый из которых содержит хотя бы одно пропущенное число. Обратите внимание, что не имеет значения, какому из интервалов мы назначаем A, если это целое число.

Мы делаем следующий проход массива, вычисляя S и Q для каждого из интервалов отдельно (но в том же проходе), и после этого отмечаем интервалы с Q = 1 и разделяем интервалы с Q> 1 . Мы продолжаем этот процесс до тех пор, пока не появятся новые «неоднозначные» интервалы, то есть нам нечего делить, потому что каждый интервал содержит ровно одно пропущенное число (и мы всегда знаем это число, потому что мы знаем S ). Мы начинаем с единственного интервала «весь диапазон», содержащего все возможные числа (как [1..N] в вопросе).

Анализ сложности времени и пространства

Общее количество проходов p, которое мы должны сделать до тех пор, пока процесс не остановится, никогда не превысит число пропущенных чисел k . Неравенство p <= k может быть строго доказано. С другой стороны, существует также эмпирическая верхняя граница p <log ₂ N + 3, которая полезна для больших значений k . Нам нужно выполнить бинарный поиск для каждого номера входного массива, чтобы определить интервал, к которому он принадлежит. Это добавляет множитель log k к сложности времени.

В общей сложности сложность по времени составляет O (N ≤ min (k, log N) ᛫ log k) . Обратите внимание, что для больших k это значительно лучше, чем для метода sdcvvc / Dimitris Andreou, который является O (N ᛫ k) .

Для своей работы алгоритм требует O (k) дополнительного пространства для хранения в большинстве k интервалов, что значительно лучше, чем O (N) в «битовых» решениях.

Реализация Java

Вот класс Java, который реализует вышеупомянутый алгоритм. Он всегда возвращает отсортированный массив пропущенных чисел. Кроме того, он не требует подсчета пропущенных чисел k, потому что вычисляет его при первом проходе. Весь диапазон чисел задается minNumberи maxNumberпараметры (например , 1 и 100 для первого примера в вопросе).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Справедливости ради, этот класс получает входные данные в виде NumberBagобъектов. NumberBagне разрешает изменение массива и произвольный доступ, а также подсчитывает, сколько раз массив был запрошен для последовательного обхода. Он также больше подходит для тестирования большого массива, чем Iterable<Integer>потому, что он позволяет избежать intупаковки примитивных значений и позволяет обернуть часть большого int[]для удобной подготовки теста. Это не трудно заменить, если это необходимо, с NumberBagпомощью int[]или Iterable<Integer>введите в findподписи, изменив два для лупов в нем в Foreach из них.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

тесты

Простые примеры, демонстрирующие использование этих классов, приведены ниже.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Тестирование большого массива может быть выполнено следующим образом:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Попробуйте их на Ideone

Я считаю , что у меня есть O(k)время и O(log(k))алгоритм пространства, учитывая , что у вас есть floor(x)и log2(x)функция для произвольно больших целых доступных:

У вас есть kдлинное целое число -бит (отсюда и log8(k)пробел), куда вы добавляете x^2, где x - это следующее число, которое вы найдете в сумке: s=1^2+2^2+...это занимает O(N)время (что не является проблемой для интервьюера). В конце вы получите j=floor(log2(s))самый большой номер, который вы ищете. Затем s=s-jи вы делаете снова выше:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Теперь у вас обычно нет функций floor и log2 для 2756целых -битных чисел, а вместо этого для удвоений. Так? Проще говоря, для каждых 2 байтов (или 1, или 3, или 4) вы можете использовать эти функции, чтобы получить желаемые числа, но это добавляет O(N)фактор к временной сложности

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

Так что, поскольку вы видите все числа, просто найдите пропавший номер. То же самое касается двух чисел. Довольно просто, я думаю. Нет смысла использовать уравнение, когда вы видите числа, оставшиеся в сумке.

Я думаю, что это можно обобщить так:

Обозначим S, M в качестве начальных значений для суммы арифметических рядов и умножения.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Я должен подумать о формуле для расчета этого, но это не главное. В любом случае, если отсутствует один номер, вы уже предоставили решение. Однако, если два числа отсутствуют, давайте обозначим новую сумму и общее кратное через S1 и M1, которые будут следующими:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Поскольку вы знаете S1, M1, M и S, вышеприведенное уравнение разрешимо найти a и b, пропущенные числа.

Теперь для трех пропавших чисел:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Теперь ваше неизвестное равно 3, а у вас есть только два уравнения, из которых вы можете решить.

Я не знаю, является ли это эффективным или нет, но я хотел бы предложить это решение.

1. Вычислить xor из 100 элементов
2. Вычислите xor из 98 элементов (после удаления 2 элементов)
3. Теперь (результат 1) XOR (результат 2) дает вам xor двух пропущенных nos i..ea XOR b, если a и b являются пропущенными элементами
   4. Получите сумму пропущенных Nos с вашим обычным приближением формула суммы diff и скажем, что разница равна d.

Теперь запустите цикл, чтобы получить возможные пары (p, q), обе из которых лежат в [1, 100] и составляют сумму d.

Когда пара получена, проверьте, является ли (результат 3) XOR p = q и если да, то все готово.

Пожалуйста, поправьте меня, если я ошибаюсь, а также прокомментируйте сложность времени, если это правильно

Мы можем делать Q1 и Q2 в O (log n) большую часть времени.

Предположим, что наш memory chipсостоит из массива nчисла test tubes. А число xв пробирке представлено x milliliterхимически-жидким.

Предположим, наш процессор является laser light. Когда мы зажигаем лазер, он проходит все трубки перпендикулярно его длине. Каждый раз, когда он проходит через химическую жидкость, светимость уменьшается на 1. И прохождение света на определенной миллилитровой отметке является операцией O(1).

Теперь, если мы зажигаем наш лазер в середине пробирки и получаем светимость

• равно предварительно рассчитанному значению (рассчитывается, когда не пропущено ни одного числа), тогда пропущенные числа больше, чем n/2.
• Если наш вывод меньше, то по крайней мере одно пропущенное число меньше, чем n/2. Мы также можем проверить, уменьшается ли светимость 1или 2. если оно уменьшается, 1то одно пропущенное число меньше, n/2а другое больше n/2. Если оно уменьшается, 2то оба числа меньше, чем n/2.

Мы можем повторить вышеописанный процесс снова и снова, сузив нашу проблемную область. На каждом этапе мы уменьшаем домен вдвое. И, наконец, мы можем добраться до нашего результата.

Параллельные алгоритмы, которые стоит упомянуть (потому что они интересны),

• сортировка по некоторому параллельному алгоритму, например, параллельное слияние может быть сделано во O(log^3 n)времени. И тогда пропущенный номер можно найти с помощью бинарного поиска по O(log n)времени.
• Теоретически, если у нас есть nпроцессоры, то каждый процесс может проверить один из входов и установить некоторый флаг, который идентифицирует число (удобно в массиве). И на следующем шаге каждый процесс может проверить каждый флаг и, наконец, вывести номер, который не помечен. Весь процесс займет O(1)время. Это O(n)требует дополнительного места / памяти.

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