2

This is a variation of [1]. I have a list of N (number of values N is known) non-negative integers. Upper bound of the list is 1024. What is the smallest non-negative integer not in the list?

For ex., the list could be 0,3,6,2,4,1,8,0,9,0 - then the output must be 5.

The way I am thinking of doing this - I know the length of the list will not be > 1024. So i have an array IFLAG of size 1024 - i then scan through the N numbers - if the i'th number is k, i set IFLAG[k] = 1. I also keep tab of the highest number in the list, say MAX

AFter scanning all N numbers in the list, I then scan IFLAG from 1 to (MAX+1) and identify the first location with a 0. That is my required output.

I have to repeatedly do this (thousands to even millions of times) - so, Is there a better way to do this (likely)?. Can i do this without using the IFLAG array?

Thanks Rey

Community
  • 1
  • 1
user1164603
  • 23
  • 2
  • 2
    Just to make sure I understand correctly, "Upper bound of the list is 1024" and "I know the length of the list will not be > 1024.", are you saying that both the max list length and the upper bound of "k" are 1024? – Joachim Isaksson Jan 23 '12 at 10:14
  • 2
    It seems to me, the size of IFLAG is bounded by the maximum value in the list, not by the length of the list. Anyway, if you cannot make any assumptions on how the list is ordered, you have to examine each item in the list atleast once. Your algorithm checks each item exactly once, thus you cannot be more efficient with respect to the length of the list (your algorithm is O(n) on the length of the list) – Rolf Rander Jan 23 '12 at 10:15
  • can you be a bit more precise about what's the input, and what's the upper bound referring to? – Savino Sguera Jan 23 '12 at 10:18
  • @JoachimIsaksson - yes, max list length and upper bound of values in the list will both be 1024. – user1164603 Jan 23 '12 at 10:20
  • @RolfRander - but i don't know the maximum value ahead of time. I only know upper bound of max value is 1024 – user1164603 Jan 23 '12 at 10:21
  • @savinos - N (number of values in a list) and the N non-negative integer values. It is not necessary that every integer that appears in the list appears only once. They can appear multiple times. – user1164603 Jan 23 '12 at 10:23
  • 1
    As long as the upper bound of the numbers is fixed and your list is unsorted, your algorithm is pretty much as sound as it can be. If gives O(n) behavior which is the lowest you can go since you have to scan the list at least once. – Joachim Isaksson Jan 23 '12 at 10:24

2 Answers2

2

Your algorithm is efficient.

It can only be improved in space complexity.

I.e. instead of an array use an int variable and set the corresponding bit.
Then check which bit is not set. You have found the missing number

Cratylus
  • 52,998
  • 69
  • 209
  • 339
0

If it is almost sorted, you can sort it in O(n) insertion sort and then find the first missing integer in O(n).

jgroenen
  • 1,332
  • 1
  • 8
  • 13