2

I found this answer: Quickest way to find missing number in an array of numbers, which is great when you have only one number missing.

Further to that question - I have wondered what is the best (and quickest) way of finding all missing numbers and also to sort the unsorted array. (for the example the array is like the one was described in the linked question - the array size is 100, with random numbers from 1-100, but some of them are missing)

Community
  • 1
  • 1
Nimrod
  • 1,100
  • 1
  • 11
  • 27
  • " I have wondered what is the best (and quickest) way of finding all missing numbers and also to sort the unsorted array" - Both at the same time? Or "quickest for sorting" and "quickest for missing numbers" independently? – Fildor Jun 16 '16 at 12:29
  • my mistake - i have meant quickest for missing numbers. – Nimrod Jun 16 '16 at 12:33
  • I don't think we can do it better than O(n), because at lease once we have to traverse the full array whether for sorting or to find the missing numbers. – pbajpai Jun 16 '16 at 12:39
  • Please use the search function before posting a question. This has been asked many times before. – m69's been on strike for years Jun 16 '16 at 14:02
  • @m69 - believe me I did. this kind of question DIDN'T asked before. the question you marked as duplicate isn't such and I refered it myself in my question noting my question is different, so instead of gaining rabish points find yourself something more important to do – Nimrod Jun 16 '16 at 15:41
  • What are rabish points? – m69's been on strike for years Jun 16 '16 at 16:37

1 Answers1

5

Obviously the numbers are in a certain range or it does not make sense to talk about missing numbers. Therefore a counting sort can be applied. Then do a linear scan through the array to find the holes. Alternatively you could scan the counts from the sorting step to find the missing elements.

This all runs in O(n).

Example: The following array is given 6,1,7,8,3,4,9,1,10,3.

Now calculate how often each number appears in the array by going once through the array and incrementing the count for each encountered number:

number 1  2  3  4  5  6  7  8  9 10
count  2  0  2  1  0  1  1  1  1  1

You immediately see that 2 and 5 did appear 0 times and are therefore missing.

The counts can also be used to come up with a sorted array: we need 2 times 1, two times 3, one time 4, and so on.

1  1  3  3  4  6  7  8  9 10
Henry
  • 42,982
  • 7
  • 68
  • 84
  • sorry for being unclear (I have edited the question). say I have an array with 10 numbers from 1 to 10 and I have for example the '2' and '5' numbers missing. can you give an example please? – Nimrod Jun 16 '16 at 12:45
  • this example is great! I don't undesrtand one small thing. you have mentioned that "it all runs on O(n)" - but I don't undesrstand why. First, you should over the array and calculate how often each number appears, which is already O(n), then when finished, you should go over and find the "holes", which is another O(n), right? So we came to O(n)^2. and if we want to sort it, it's another O(n). Did I get it wrong? – Nimrod Jun 18 '16 at 07:06
  • 1
    Almost correct, but O(n) + O(n) is still O(n) so in total we get O(n) + O(n) + O(n) which sums up to O(n). – Henry Jun 18 '16 at 07:50