Find missing number in sequence in set or list

Question

If a std::set or std::list contains a sequence of natural numbers (1, 2, 3..). would there be a function in standard library to find the missing number?

Answer 1

None specifically for that purpose (the standard algorithms try to be a bit more generalized). You could, however, use std::accumulate for one fairly large piece of the work.

Hint: the sum of a set of numbers from 1..N is (N+1)*(N/2).

Edit: my idea of an answer is to subtract the sum of you the numbers you have from the sum you'd get if all the numbers were present. That difference will be the missing number.

#include <numeric>
#include <iostream>

#define elements(x) (sizeof(x)/sizeof(x[0]))

int main() { 
    int x[] = {8, 4, 3, 5, 1, 2, 7}; 


    int N = elements(x) +1;

    int projected_sum = (N+1)*(N/2);
    int actual_sum = std::accumulate(x, x+elements(x), 0);

    std::cout << "The missing number is: " << projected_sum - actual_sum << "\n";
    return 0;
}

For the moment, this ignores a few minor details like what happens if the set has an odd number of elements, but should show the general idea. I've also used an array instead of a list, simply for ease of initialization. I haven't used anything like random access that a list can't (reasonably) support. This has linear complexity, and as you can see from the sample input, doesn't require the input to be sorted.

Edit2: if the intent is that the input is in sorted order, I'd probably do the job a bit differently: just walk through and find an item that isn't exactly one greater than its predecessor.

Answer 2

You could std::mismatch() with a sequence of natural numbers. To save space, I think boost::counting_iterator works wonders here:

#include <iostream>
#include <list>
#include <boost/iterator/counting_iterator.hpp>
int main()
{
    std::list<int> l = {1,2,3,4,6,7,8,9};
    auto i = mismatch(l.begin(), l.end(), boost::counting_iterator<int>(1));
    if(i.first==l.end())
            std::cout << "no missing numbers\n";
    else
            std::cout << "the first missing number is " << *i.second << '\n';

}

test run:

~ $ g++ -std=c++0x -pedantic -Wall -Wextra -o test test.cc
~ $ ./test
the first missing number is 5

Answer 3

You can find all missing numbers using set_difference and a custom iterator:

class seqIter : public std::iterator<std::input_iterator_tag, int> {
public:
    seqIter(int n) : num(n) {}
    seqIter(const seqIter & n) : num(n.num) {}
    int & operator *() {return num;}
    seqIter & operator ++() { ++num; return *this; }
    bool operator !=(const seqIter & n) { return n.num != num; }
private:
    int num;
};

int main(int argc, char *argv[])
{
    int n[] = { 1, 3, 4, 7, 10 };
    std::set<int>   numbers(n, n + sizeof(n)/sizeof(n[0]));
    std::set<int>   missing;
    std::set_difference(    seqIter(*numbers.begin()+1), seqIter(*numbers.rbegin()), 
                            numbers.begin(), numbers.end(),
                            std::insert_iterator<std::set<int> >(missing, missing.begin())
                        );
}

It's probably not any faster than going thru the numbers with a for loop though.