5

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 ?

sanz
  • 1,069
  • 1
  • 10
  • 26
  • 1
    Could you please write down the one scan algo? Thanks. – Summer_More_More_Tea Nov 09 '12 at 02:25
  • This question seems very localized and you also haven't given any evidence that you have tried to solve the problem yourself. – lockstock Nov 09 '12 at 02:28
  • @lockstock sorry about that. I have edited the question. Hope this helps. – sanz Nov 09 '12 at 02:38
  • This is a frequent interview questions. I believe once M is big enough, solving it with O(1) extra memory is not possible. If you use more than O(1) extra memory, it's unlikely that you won't need to scan that memory once. You definitely need to scan the original array once. And that would be twice already. – Haozhun Nov 09 '12 at 02:43
  • 2
    See top answer here: http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe – Ismail Badawi Nov 09 '12 at 03:44
  • @isbadawi Wow, linked to answer is incredible as a mathematical solution, but sort of insane as a programming solution. – A. Webb Nov 09 '12 at 04:17

1 Answers1

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.

A. Webb
  • 26,227
  • 1
  • 63
  • 95
  • But don't you have to loop through the linked list to print out the missing integers? It's `>1` loop as I understand it? – irrelephant Nov 09 '12 at 04:41
  • @irrelephant You bet, assuming you wish to print them. I don't think you can do better from a time complexity standpoint that `O(N) + O(M)` because until you reach the reach the end of `N` you cannot know the last of the missing from the `M`. If you had already started printing, the last of the `N` could spoil your output by containing something you already printed. I'm sure you can probably do better from a space complexity perspective when M< – A. Webb Nov 09 '12 at 04:59
  • I shouldn't have used Big-O notation there. I meant to say I don't think you can't do better than a single pass through `N` and `M` if you want to print `M`. – A. Webb Nov 09 '12 at 05:15