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;
    }
};

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;
    }
};

To copy to clipboard, switch view to plain text mode