Given an unordered list of integers, return a value not present in the list

Question

I have an algorithm problem that I came across at work but have not been able to come up with a satisfactory solution for. I browsed this forum some and the closest I have come to the same problem is How to find a duplicate element in an array of shuffled consecutive integers?.

I have a list of N elements of integers which can contain the elements 1-M (M>N), further the list is unsorted. I want a function that will take this list as input and return a value in range 1-M not present in the list. The list contains no duplicates. I was hoping for an o(N) solution, with out using additional space UPDATE: function cannot change the original list L

for instance N = 5 M = 10 List (L): 1, 2, 4, 8, 3 then f(L) = 5 To be honest i dont care if it returns an element other than 5, just so long as it meets the contraints above

The only solution I have come up with so far is using an additional array of M elements. Walking through the input list and setting the corresponding array elements to 1 if present in the list. Then iterating over this list again and returning the index of the first element with value 0. As you can see this uses additional o(M) space and has complexity 2*o(N). Any help would we appreciated.

Thanks for the help everyone. The stack overflow community is definitely super helpful. To give everyone a little more context of the problem I am trying to solve. I have a set of M token that I give out to some clients (one per client). When a client is done with the token they get returned to my pile. As you can see the original order I give client a token is sorted.
so M = 3     Tokens
client1: 1          <2,3>
client2: 2          <3>
client1 return: 1  <1,3>
client 3: 3        <1>
Now the question is giving client4 token 1. I could at this stage give client 4 token 2 and sort the list. Not sure if that would help. In any case if I come up with a nice clean solution I will be sure to post it
Just realised I might have confused everyone. I do not have the list of free token with me when I am called. I could statically maintain such a list but I would rather not

Answer 1

You can do divide and conquer. Basically given the range 1..m, do a quicksort style swapping with m/2 as the pivot. If there are less than m/2 elements in the first half, then there is a missing number and iteratively find it. Otherwise, there is a missing number in the second half. Complexity: n+n/2+n/4... = O(n)

def findmissing(x, startIndex, endIndex, minVal, maxVal):
    pivot = (minVal+maxVal)/2
    i=startIndex
    j=endIndex
    while(True):
        while( (x[i] <= pivot) and (i<j) ):
            i+=1
        if i>=j:
            break
        while( (x[j] > pivot) and (i<j) ):
            j+=1
        if i>=j:
            break
        swap(x,i,j)
     k = findlocation(x,pivot)
     if (k-startIndex) < (pivot-minVal):
         findmissing(x,startIndex, k, minVal, pivot)
     else:
         findmissing(x, k+1, endIndex, pivot+1, maxVal)

I have not implemented the end condition which I will leave it to you.

Answer 2

You can have O(N) time and space. You can be sure there is an absent element within 1..N+1, so make an array of N+1 elements, and ignore numbers larger than N+1.

If M is large compared to N, say M>2N, generate a random number in 1..M and check if it is not on the list in O(N) time, O(1) space. The probability you will find a solution in a single pass is at least 1/2, and therefore (geometric distribution) the expected number of passes is constant, average complexity O(N).

If M is N+1 or N+2, use the approach described here.

Answer 3

Can you do something like a counting sort? Create an array of size (M-1) then go through the list once (N) and change the array element indexed at i-1 to one. After looping once through N, search 0->(M-1) until you find the first array with a zero value.

Should me O(N+M).

Array L of size (M-1): [0=0, 1=0, 2=0, 3=0, 4=0, 5=0, 6=0, 7=0, 8=0, 9=0]

After looping through N elements: [0=1, 1=1, 2=1, 3=1, 4=0, 5=0, 6=0, 7=1, 8=0, 9=0]

Search array 0->(M-1) finds index 4 is zero, therefore 5 (4+1) is the first integer not in L.

Answer 4

After reading your updated i guess you are making it over complex. First of all let me list down what i get from your question

• Yoou need to give a token to the client regardless of its order, quoting from your original post

for instance N = 5 M = 10 List (L): 1, 2, 4, 8, 3 then f(L) = 5 To be honest i dont care if it returns an element other than 5, just so long as it meets the contraints above

• Secondly, you are already mantaining a list of "M" Tokens
• Client is fetching the token and after using it returning it back to you

Given these 2 points, why don't you implement a TokenPool?

• Implement your M list based on a Queue
• Whenever a client ask for a a token, fetch a token from the queue i.e. removing it from queue. By this method, your queue will always maintain those tokens which aren't given away. you are doing it O(1)
• Whenever a client is done with the token he will return it back to you. Add it back to the queue. Again O(1).

In whole implementation, you wouldn't have to loop through any of list. All you have to do is to Generate the token and insert in the queue.