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

You can use a set data structure - one for all the numbers up to N, one for the numbers you actually saw, and use a set difference.

Answer 2

One way to do this would be to look at each element of the array in sequence, and see whether that element has been seen before in elements that you've already checked. If so, then change that number to one you haven't seen before, and proceed.

Allow me to introduce you to my friend Schlemiel the Painter. Discovery of a more efficient method is left as a challenge for the reader.

Answer 3

This kind of looks like homework, please let us know if it isn't. I'll give you a small hint, and then I'll improve my answer if you confirm this isn't homework.

My tip for now is this: If you were to do this by hand, how would you do it? Would you write out an extra list of numbers of some time, would you read through the list (how many times?)? etc.

For simple problems, sometimes modelling your algorithm after an intuitive by-hand approach can work well.

Answer 4

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.

Answer 5

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 6

Here's a link I read just today that may be helpful. http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html