Minimum excluded value (tools/mex.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-01-07 15:56:46+09:00
• Include: #include "tools/mex.hpp"

template <typename InputIterator>
std::decay_t<decltype(*std::declval<InputIterator>())> mex(InputIterator begin, InputIterator end);

It returns the minimum non-negative integer which is not in a given sequence.

Constraints

• begin $\leq$ end
• std::decay_t<decltype(*std::declval<InputIterator>())> is an integral type.
• All the integers in the sequence are non-negative.

Time Complexity

• $O(n)$ where $n$ is end - begin

License

• CC0

Author

• anqooqie

Required by

• Longest common substring (tools/longest_common_substring.hpp)
• Manacher (tools/manacher.hpp)
• Range count distinct (tools/range_count_distinct.hpp)

Verified with

• tests/longest_common_substring.test.cpp
• tests/manacher.test.cpp
• tests/mex.test.cpp
• tests/range_count_distinct.test.cpp

Code

#ifndef TOOLS_MEX_HPP
#define TOOLS_MEX_HPP

#include <type_traits>
#include <utility>
#include <vector>
#include <cstddef>
#include <cassert>
#include <algorithm>

namespace tools {

  template <typename InputIterator>
  ::std::decay_t<decltype(*::std::declval<InputIterator>())> mex(InputIterator begin, InputIterator end) {
    using T = ::std::decay_t<decltype(*::std::declval<InputIterator>())>;
    const ::std::vector<T> orig(begin, end);
    const ::std::size_t n = orig.size();

    assert(::std::all_of(orig.begin(), orig.end(), [](const auto& o) { return o >= 0; }));

    ::std::vector<bool> exists(n, false);
    for (const ::std::size_t o : orig) {
      if (o < n) {
        exists[o] = true;
      }
    }
    for (::std::size_t i = 0; i < n; ++i) {
      if (!exists[i]) {
        return i;
      }
    }
    return n;
  }
}

#endif

#line 1 "tools/mex.hpp"



#include <type_traits>
#include <utility>
#include <vector>
#include <cstddef>
#include <cassert>
#include <algorithm>

namespace tools {

  template <typename InputIterator>
  ::std::decay_t<decltype(*::std::declval<InputIterator>())> mex(InputIterator begin, InputIterator end) {
    using T = ::std::decay_t<decltype(*::std::declval<InputIterator>())>;
    const ::std::vector<T> orig(begin, end);
    const ::std::size_t n = orig.size();

    assert(::std::all_of(orig.begin(), orig.end(), [](const auto& o) { return o >= 0; }));

    ::std::vector<bool> exists(n, false);
    for (const ::std::size_t o : orig) {
      if (o < n) {
        exists[o] = true;
      }
    }
    for (::std::size_t i = 0; i < n; ++i) {
      if (!exists[i]) {
        return i;
      }
    }
    return n;
  }
}

Back to top page