Algorithm for smallest number not in a list

[zeldaknight]

Hi,
I was wondering if anyone has an easy way to get the lowest number not in a set.
For example:
A set of numbers (1,2,3,4,6,7,10)

I need an algorithm that will generate 5,8,9,11,13,...
Does anyone have an easy solution? I could probably work it out myself, but if someone already has an algorithm (any language - I'm using C++/Qt) then that would save me some effort ;)

Thanks!

[aamer4yu]

What will be the range of numbers ? you will need to define the range of numbers.

Also will you set be a large or small one ? If small, you can do with brute force... else, some good algo needs to be thought of.

[Ginsengelf]

Hi, for a small range of numbers, you could first create a complete set, then use std::set_difference() from the <algorithm>. For larger ranges this is probably not the smartest approach :)

Ginsengelf

[RufusVS]

We have to assume these are integers, but are they in ascending order?

int number_set[] = {1,2,3,4,5, 7,8,9,10}; // for example

int index = 1;

while (index == number_set[index-1]) ++index;

cout << "missing " << index;

for a trivial example.

If they are not in sequence, I might use the values to set bits an a bit array, then find the
lowest bit not set.

I hope this isn't a homework assignment.

Rufus

[Coises]

Not tested, but I think this is close to what you want:
class MissingNumbers {
private:
QList<int> numbers;
int count;
int index;
int last;
public:
MissingNumbers(const QSet<int> &numbersWeHave) {
numbers.fromSet(numbersWeHave);
qSort(numbers);
count = numbers.count();
index = 0;
last = 0;
}
int next() {
++last;
if (index >= count || last < numbers.at(index)) return last;
while (++index < count && numbers.at(index) - numbers.at(index-1) <= 1);
return last = numbers.at(index-1) + 1;
}
};