## Algorithm to find first available number

So recently I stumbled across a programming quiz to which I later returned because it somehow fascinated me.

### Problem

Finding the first available number (or the smallest missing number) in a list is a common problem in Computer Science (for example for Defragmenting or generating keys) and describes the search for the smallest natural number, which is not part of a set X of natural numbers. X is a set of distinct natural numbers (and being a set, is not ordered).

**We are now looking for a function with linear worst-case time complexity O(n).**

### Example

We define X as a set of distinct natural numbers:

X = {23,9,12,0,11,1,13,7,21,14,5,4,17,19,3,6,2}

So in this set, we find that the number **8** is the first available number (smallest missing number). So running the algorithm over the above set should return 8.

Read the rest of this entry »