Argthtjtr

Random methods are indeed very efficient here.

If we want to use a deterministic method and by assuming the size n is not too large, 4000 for example, then we can create a vector x of size m = n + 1 (or a little bit larger, 4096 for example to facilitate calculation), initialised with 0.

For each i in the range, we just set x[array[i] modulo m] = 1.

Then a simple O(n) search in x will provide a value which is not in array

Note: the modulo operation is not exactly the "%" operation

Edit: I mentioned that calculations are made easier by selecting here a size of 4096. To be more concrete, this implies that the modulo operation is performed with a simple & operation

You can find the smallest unused integer in O(N) time using O(1) auxiliary space if you are allowed to reorder the input vector, using the following algorithm. [Note 1] (The algorithm also works if the vector contains repeated data.)

size_t smallest_unused(std::vector<unsigned>& data) {

  size_t N = data.size(), scan = 0;

  while (scan < N) {

    auto other = data[scan];

    if (other < scan && data[other] != other) {

      data[scan] = data[other];

      data[other] = other;

    }

    else

      ++scan;

  }

  for (scan = 0; scan < N && data[scan] == scan; ++scan) { }

  return scan;

}

The first pass guarantees that if some k in the range [0, N) was found after position k, then it is now present at position k. This rearrangement is done by swapping in order to avoid losing data. Once that scan is complete, the first entry whose value is not the same as its index is not referenced anywhere in the array.

That assertion may not be 100% obvious, since a entry could be referenced from an earlier index. However, in that case the entry could not be the first entry unequal to its index, since the earlier entry would be meet that criterion.

To see that this algorithm is O(N), it should be observed that the swap at lines 6 and 7 can only happen if the target entry is not equal to its index, and that after the swap the target entry is equal to its index. So at most N swaps can be performed, and the if condition at line 5 will be true at most N times. On the other hand, if the if condition is false, scan will be incremented, which can also only happen N times. So the if statement is evaluated at most 2N times (which is O(N)).

Notes:

1. I used unsigned integers here because it makes the code clearer. The algorithm can easily be adjusted for signed integers, for example by mapping signed integers from [INT_MIN, 0) onto unsigned integers [INT_MAX, INT_MAX - INT_MIN) (The subtraction is mathematical, not according to C semantics which wouldn't allow the result to be represented.) In 2's-complement, that's the same bit pattern. That changes the order of the numbers, of course, which affects the semantics of "smallest unused integer"; an order-preserving mapping could also be used.

Make random x (INT_MIN..INT_MAX) and test it against all. Test x++ on failure (very rare case for 40/400/4000).

Step 1: Sort the vector.

That can be done in O(n log(n)), you can find a few different algorithms online, use the one you like the most.

Step 2: Find the first int not in the vector.

Easily iterate from INT_MIN to INT_MIN + 40/400/4000 checking if the vector has the current int:

Pseudocode:

SIZE = 40|400|4000 // The one you are using

for (int i = 0; i < SIZE; i++) {

    if (array[i] != INT_MIN + i)

        return INT_MIN + i;

The solution would be O(n log(n) + n) meaning: O(n log(n))

Edit: just read your edit asking for something better than O(n log(n)), sorry.

For the case in which the integers are provided in an std::unordered_set<int> (as opposed to a std::vector<int>), you could simply traverse the range of integer values until you come up against one integer value that is not present in the unordered_set<int>. Searching for the presence of an integer in an std::unordered_set<int> is quite straightforward, since std::unodered_set does provide searching through its find() member function.

The space complexity of this approach would be O(1).

If you start traversing at the lowest possible value for an int (i.e., std::numeric_limits<int>::min()), you will obtain the lowest int not contained in the std::unordered_set<int>:

int find_lowest_not_contained(const std::unordered_set<int>& set) {

   for (auto i = std::numeric_limits<int>::min(); ; ++i) {

      auto it = set.find(i); // search in set

      if (it == set.end()) // integer not in set?

         return *it;

   }

}

Analogously, if you start traversing at the greatest possible value for an int (i.e., std::numeric_limits<int>::max()), you will obtain the lowest int not contained in the std::unordered_set<int>:

int find_greatest_not_contained(const std::unordered_set<int>& set) {

   for (auto i = std::numeric_limits<int>::max(); ; --i) {

      auto it = set.find(i); // search in set

      if (it == set.end()) // integer not in set?

         return *it;

   }

}

Assuming that the ints are uniformly mapped by the hash function into the unordered_set<int>'s buckets, a search operation on the unordered_set<int> can be achieved in constant time. The run-time complexity would then be O(M ), where M is the size of the integer range you are looking for a non-contained value. M is upper-bounded by the size of the unordered_set<int> (i.e., in your case M <= 4000).

Indeed, with this approach, selecting any integer range whose size is greater than the size of the unordered_set, is guaranteed to come up against an integer value which is not present in the unordered_set<int>.