- A+

Related to the classic problem find an integer not among four billion given ones but not exactly the same.

To clarify, by *integers* what I really mean is only a subset of its mathemtical definition. That is, assume there are only finite number of integers. Say in C++, they are `int`

in the range of `[INT_MIN, INT_MAX]`

.

Now given a `std::vector<int>`

(no duplicates) or `std::unordered_set<int>`

, whose size can be 40, 400, 4000 or so, but not too large, how to efficiently generate a number that is guaranteed to be not among the given ones?

If there is no worry for overflow, then I could multiply all nonzero ones together and add the product by 1. But there is. The adversary test cases could delibrately contain `INT_MAX`

.

I am more in favor of simple, non-random approaches. Is there any?

Thank you!

*Update: to clear up ambiguity, let's say an unsorted std::vector<int> which is guaranteed to have no duplicates. So I am asking if there is anything better than O(n log(n)). Also please note that test cases may contain both INT_MIN and INT_MAX.*

You could just return the first of `N+1`

candidate integers not contained in your input. The simplest candidates are the numbers `0`

to `N`

. This requires `O(N)`

space and time.

` int find_not_contained(container<int> const&data) { const int N=data.size(); std::vector<char> known(N+1, 0); // one more candidates than data for(int i=0; i< N; ++i) if(data[i]>=0 && data[i]<=N) known[data[i]]=1; for(int i=0; i<=N; ++i) if(!known[i]) return i; assert(false); // should never be reached. } `

Random methods can be more space efficient, but may require more passes over the data in the worst case.