Will Dean Will Dean - 1 month ago 9
C++ Question

Finding gaps in sequence of numbers

I have a std::vector containing a handful of numbers, which are not in any particular order, and may or may not have gaps between the numbers - for example, I may have { 1,2,3, 6 } or { 2,8,4,6 } or { 1, 9, 5, 2 }, etc.

I'd like a simple way to look at this vector and say 'give me the lowest number >= 1 which does not appear in the vector'. So,

for the three examples above, the answers would be 4, 1 and 3 respectively.

It's not performance critical, and the list is short so there aren't any issues about copying the list and sorting it, for example.

I am not really stuck for a way to do this, but my STL skills are seriously atrophied and I can feel that I'm about to do something inelegant - I would be interested to see what other people came up with.

Answer

The checked answer uses < for comparison. != is much simpler:

int find_gap(std::vector<int> vec) {
    std::sort(vec.begin(), vec.end());
    int next = 1;
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        if (*it != next) return next;
       ++next;
    }
    return next;
}

find_gap(1,2,4,5) = 3
find_gap(2) = 1
find_gap(1,2,3) = 4

I'm not passing a reference to the vector since a) he said time doesn't matter and b) so I don't change the order of the original vector.

Comments