Find two missing numbers

Question

We have a machine with O(1) memory and we want to pass n numbers (one by one) in the first pass, and then we exclude the two numbers and we will pass n-2 numbers to the machine.

write an algorithm that finds missing numbers.

Answer 1

It can be done with O(1) memory.

You only need a few integers to keep track of some running sums. The integers do not require log n bits (where n is the number of input integers), they only require 2b+1 bits, where b is the number of bits in an individual input integer.

When you first read the stream add all the numbers and all of their squares, i.e. for each input number, n, do the following:

sum += n
sq_sum += n*n

Then on the second stream do the same thing for two different values, sum2 and sq_sum2. Now do the following maths:

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

You need 2b+1 bits in all intermediate results because you are storing products of two input integers, and in one case multiplying one of those values by two.

Answer 2

Assuming the numbers are ranging from 1..N and 2 of them are missing - x and y, you can do the following:

Use Gauss formula: sum = N(N+1)/2

sum - actual_sum = x + y

Use product of numbers: product = 1*2..*N = N!

product - actual_product = x * y

Resolve x,y and you have your missing numbers.

In short - go through the array and sum up each element to get the actual_sum, multiply each element to get actual_product. Then resolve the two equations for x an y.

Answer 3

It cannot be done with O(1) memory.

Assume you have a constant k bits of memory - then you can have 2^k possible states for your algorithm.

However - input is not limited, and assume there are (2^k) + 1 possible answers for (2^k) + 1 different problem cases, from piegeonhole principle, you will return the same answer twice for 2 problems with different answers, and thus your algorithm is wrong.

Answer 4

The following came to my mind as soon as I finished reading the question. But the answers above suggest that it is not possible with O(1) memory or that there should be a constraint on the range of numbers. Tell me if my understanding of the question is wrong. Ok, so here goes

You have O(1) memory - which means you have constant amount of memory.

When the n numbers are passed to you 1st time, just keep adding them in one variable and keep multiplying them in another. So at the end of 1st pass you have the sum and product of all the numbers in 2 variables S1 and P1. You have used 2 variable till now (+1 if you reading the numbers in memory).

When the (n-2) numbers are passed to you the second time, do the same. Store the sum and product of the (n-2) numbers in 2 other variables S2 and P2. You have used 4 variables till now (+1 if you reading the numbers in memory).

If the two missing numbers are x and y, then

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

You have two equations in two variables. Solve them.

So you have used a constant amount of memory (independent of n).

Answer 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);
}

Answer 6

Please look at the solution link below. It explains an XOR method. This method is more efficient than any of the methods explained above. It might be the same as Victor above, but there is an explanation as to why this works.

Solution here

Answer 7

Here is the simple solution which does not require any quadratic formula or multiplication:

Let say B is the sum of two missing numbers.

The set of two missing numbers will be one from: (1,B-1),(2,B-1)...(B-1,1)

Therefore, we know that one of those two numbers will be less than or equal to the half of B.

We know that we can calculate the B (sum of both missing number).

So, once we have B, we will find the sum of all numbers in the list which are less than or equal to B/2 and subtract that from the sum of (1 to B/2) to get the first number. And then, we get the second number by subtracting first number from B. In below code, rem_sum is B.

public int[] findMissingTwoNumbers(int [] list, int N){
    if(list.length == 0 || list.length != N - 2)return new int[0];

    int rem_sum = (N*(N + 1))/2;
    for(int i = 0; i < list.length; i++)rem_sum -= list[i];

    int half = rem_sum/2;
    if(rem_sum%2 == 0)half--; //both numbers cannot be the same
    int rem_half = getRemHalf(list,half);

    int [] result = {rem_half, rem_sum - rem_half};
    return result;
}
private int getRemHalf(int [] list, int half){
    int rem_half = (half*(half + 1))/2;
    for(int i = 0; i < list.length; i++){
        if(list[i] <= half)rem_half -= list[i];
    }
    return rem_half;
}