Найдите два недостающих номера

Ответ 1

Это можно сделать с помощью O (1) памяти.

Вам нужно всего несколько целых чисел, чтобы отслеживать некоторые текущие суммы. Целые числа не требуют бит log n (где n - число целых чисел), они требуют только 2b + 1 бит, где b - количество бит в отдельном входном целое.

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

sum += n
sq_sum += n*n

Затем во втором потоке сделайте то же самое для двух разных значений: sum2 и sq_sum2. Теперь сделайте следующую математику:

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

Вам нужны 2b + 1 бит во всех промежуточных результатах, потому что вы храните продукты из двух целых чисел и в одном случае умножаете одно из этих значений на два.

Ответ 2

Предполагая, что числа варьируются от 1..N и 2 из них отсутствуют - x и y, вы можете сделать следующее:

Использовать формулу Гаусса: sum = N(N+1)/2

sum - actual_sum = x + y

Использовать произведение чисел: product = 1*2..*N = N!

product - actual_product = x * y

Разрешите x, y и у вас есть недостающие номера.

Короче - пройдите через массив и суммируйте каждый элемент, чтобы получить actual_sum, умножьте каждый элемент на получение actual_product. Затем разрешите два уравнения для x a y.

Ответ 3

Это невозможно сделать с помощью O(1) памяти.

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

Однако - вход не ограничен, и предположим, что существуют (2^k) + 1 возможные ответы для (2^k) + 1 различных проблемных ситуаций, из принцип piegeonhole, вы дважды вернете тот же ответ для двух проблем с разными ответами, и, следовательно, ваш алгоритм неверен.

Ответ 4

Мне пришло в голову, как только я закончил читать вопрос. Но приведенные выше ответы позволяют предположить, что это невозможно с памятью O (1) или что ограничение диапазона должно быть ограничено. Скажите, если мое понимание вопроса неверно. Итак, здесь идет

У вас есть O (1) память, что означает, что у вас постоянный объем памяти.

Когда числа n передаются вам в первый раз, просто добавьте их в одну переменную и продолжайте умножать их на другую. Итак, в конце 1-го прохождения у вас есть сумма и произведение всех чисел в 2 переменных S1 и P1. Вы использовали 2 переменные до сих пор (+1, если вы читаете цифры в памяти).

Когда номера (n-2) передаются вам во второй раз, сделайте то же самое. Сохраните сумму и произведение чисел (n-2) в двух других переменных S2 и P2. До сих пор вы использовали 4 переменные (+1, если вы читаете цифры в памяти).

Если два отсутствующих числа: x и y, то

x + y = S1 - S2
x*y = P1/P2;

У вас есть два уравнения в двух переменных. Решите их.

Итак, вы использовали постоянный объем памяти (независимо от n).

Ответ 5

void Missing(int arr[], int size)
{
  int xor = arr[0]; /* Will hold xor of all elements */
  int set_bit_no;  /* Will have only single set bit of xor */
  int i;
  int n = size - 2;
  int x = 0, y = 0;

  /* Get the xor of all elements in arr[] and {1, 2 .. n} */
  for(i = 1; i < size; i++)
    xor ^= arr[i];  
  for(i = 1; i <= n; i++)
    xor ^= i;   

  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor & ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i < size; i++)
  {
    if(arr[i] & set_bit_no)
      x = x ^ arr[i]; /*XOR of first set in arr[] */
    else
      y = y ^ arr[i]; /*XOR of second set in arr[] */
  }
  for(i = 1; i <= n; i++)
  {
    if(i & set_bit_no)
      x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
    else
      y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
  }

  printf("\n The two repeating missing elements are are %d & %d ", x, y);
}