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

Ответ 1

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

Запомните сумму 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

...

c _k= a ₁ a ₂... 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.

Ответ 2

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

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

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

Ответ 3

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

Тогда мы можем свести задачу к

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

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

Подстановка дает нам:

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

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

Ответ 4

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

Предполагая, что "сумка" представлена ​​массивом размером A[] размером N - k 1, мы можем решить 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 должно быть отсутствовать.

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

Проблема с решениями, основанными на суммах чисел, заключается в том, что они не учитывают стоимость хранения и работы с числами с большими показателями... на практике, поскольку он работает для очень больших 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)`

So 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-я запись в сумке, 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)) Этот алгоритм более интуитивно понятен, имеет одинаковую временную сложность и использует меньше места.

Ответ 9

Подождите минуту. Как говорится в этом вопросе, в сумке насчитывается 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.

Ответ 10

Здесь решение, которое использует 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; }
    }
}

Ответ 11

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

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

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

• a) Если в каждом разделе отсутствует одно число, используйте разницу суммного подхода для поиска каждого недостающего номера.

  (1 + 2 + ... + (p-1)) - sum(l) = missing #1 и ((p+1) + (p+2) ... + n) - sum(r) = missing #2

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

  Если одному разделу не хватает двух чисел, но не пуст, перезапустите его на этот partiton.

Только с двумя недостающими числами этот алгоритм всегда отбрасывает хотя бы один раздел, поэтому он сохраняет O(n) среднюю временную сложность quickselect. Аналогично, с 3 недостающими числами этот алгоритм также отбрасывает по крайней мере один раздел с каждым проходом (поскольку, как и в случае с двумя отсутствующими номерами, максимум 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);
    }
  }

Демо

Ответ 12

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

S = сумма всех чисел в сумке (S < 5050)
Z = сумма недостающих чисел 5050 - S

если недостающие цифры x и y, а затем:

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

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

Ответ 13

Может быть, этот алгоритм может работать для вопроса 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 будут лежать в разных сегментах. Теперь повторите то же самое, что мы сделали для нахождения одного недостающего элемента в каждом ведре.

Ответ 14

Вы можете решить 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, сокращения и суммирования, поэтому я не могу решить сложность этого решения (если кто-нибудь знает, пожалуйста, прокомментируйте ниже).

Ответ 15

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

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

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

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

Ответ 16

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

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

# чисел в сумке = n

# недостающих чисел = k

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

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

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

Eg. Первоначально сумка выглядит как [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;
    }

Ответ 17

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

• Сделайте массив a размером u = k^2.
• Выберите любую , h : {1,...,n} -> {1,...,u}. (Как multiply-shift)
• Для каждого 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 в случае энергетических сумм.

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

Ответ 18

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

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

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

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

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

Ответ 19

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

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

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

Ответ 20

Я бы взял другой подход к этому вопросу и исследовал интервьюера для получения более подробной информации о более крупной проблеме, которую он пытался решить. В зависимости от проблемы и требований, связанных с ней, очевидное решение на основе набора может быть правильным, а метод generate-a-list-and-pick-through-it-afterward не может быть.

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

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

Ответ 21

Вы можете мотивировать решение, думая об этом в терминах симметрии (группы, в математическом языке). Независимо от порядка набора чисел, ответ должен быть таким же. Если вы собираетесь использовать функции 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.

Ответ 22

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

Предположим, у нас есть номера от 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 * x) -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.

Ответ 23

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

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

Ответ 24

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

Ответ 25

Я считаю, что есть пробел времени 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 -bit, но вместо этого для парных. Так? Просто для каждого 2 байта (или 1, или 3 или 4) вы можете использовать эти функции для получения желаемых номеров, но это добавляет фактор O(N) к временной сложности

Ответ 26

Я думаю, что это можно обобщить следующим образом:

Обозначим 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, в то время как у вас есть только два уравнения, из которых вы можете решить.

Ответ 27

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

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

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

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

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

Ответ 28

Мы можем делать 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) пространства/памяти.

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

Ответ 29

$removedNumbers = array_flip(range(50, 200));

foreach($secretNumberBagRange_50_200 as $value) {
    unset($removedNumbers[$value]);
}

Ответ 30

Попробуйте найти произведение чисел от 1 до 50:

Пусть произведение, P1 = 1 x 2 x 3 x............. 50

Когда вы вынимаете номера один за другим, умножьте их так, чтобы вы получили продукт P2. Но здесь отсутствуют два числа, следовательно, P2 < Р1.

Произведение двух сходящихся членов, a x b = P1 - P2.

Вы уже знаете сумму, a + b = S1.

Из приведенных выше двух уравнений, разрешите для a и b через квадратичное уравнение. a и b - ваши недостающие номера.