Find the numbers missing

Question

If we have an array of all the numbers up to N (N < 10), what is the best way to find all the numbers that are missing. Example:

N = 5
1 5 3 2 3

Output: 1 5 4 2 3 

In the ex, the number 4 was the missing one and there were 2 3s, so we replaced the first one with 4 and now the array is complete - all the numbers up to 5 are there.

Is there any simple algorithm that can do this ?

Answer 1

Since N is really small, you can use F[i] = k if number i appears k times.

int F[10]; // make sure to initialize it to 0
for ( int i = 0; i < N; ++i )
  ++F[ numbers[i] ];

Now, to replace the duplicates, traverse your number array and if the current number appears more than once, decrement its count and replace it with a number that appears 0 times and increment that number's count. You can keep this O(N) if you keep a list of numbers that don't appear at all. I'll let you figure out what exactly needs to be done, as this sounds like homework.

Answer 2

Assume all numbers within the range 1 ≤ x ≤ N.

Keep 2 arrays of size N. output, used (as an associative array). Initialize them all to 0.

Scan from the right, fill in values to output unless it is used.

Check for unused values, and put them into the empty (zero) slots of output in order.

O(N) time complexity, O(N) space complexity.