m integers missing from an array of size n

Question

This is an interesting question I had come across a while ago and had some trouble solving it.

There's an unsorted integer array of size N stored with numbers 1,2..,N+M , with M integers missing from it. M and N are known before hand. Write an algorithm to find the missing M integers in the most efficient manner.

Had tried mapping it to an array of size N + M, so that the i th index contains the element with value i, but this requires 2 scans (1 for mapping, 1 for finding the M missing numbers).

The book in which I came across this mentions a single scan solution is possible but I was not able to arrive at it. Any ideas on how to go about this ?

Answer 1

You can do this with a doubly linked list mapped on top of an array.

position 1 2 3 4 5 6 ...
next     2 3 4 5 6 7 ...
prev     0 1 2 3 4 5 ...

On the pass through the input you index into the position corresponding to each input number and update the linked list to remove (skip over) that position from the linked list. At the end of the input the linked list will contain only the positions not visited.