Minimum Excluded Value ($O(n)$ for a given sorted container)
(utils/mex.hpp)

• View this file on GitHub
• Last update: 2020-07-27 01:00:36+09:00
• Include: #include "utils/mex.hpp"
• Link: https://en.wikipedia.org/wiki/Mex_(mathematics)

Code

#pragma once
#include <cassert>

/**
 * @brief Minimum Excluded Value ($O(n)$ for a given sorted container)
 * @sa https://en.wikipedia.org/wiki/Mex_(mathematics)
 * @note xs must be weakly increasing
 */
template <typename InputIterator>
int mex(InputIterator first, InputIterator last) {
    int last_x = 0;  // only for debug
    int y = 0;
    for (; first != last; ++ first) {
        int x = *first;
        assert (last_x <= x);
        last_x = x;
        if (y < x) break;
        if (y == x) ++ y;
    }
    return y;
}

#line 2 "utils/mex.hpp"
#include <cassert>

/**
 * @brief Minimum Excluded Value ($O(n)$ for a given sorted container)
 * @sa https://en.wikipedia.org/wiki/Mex_(mathematics)
 * @note xs must be weakly increasing
 */
template <typename InputIterator>
int mex(InputIterator first, InputIterator last) {
    int last_x = 0;  // only for debug
    int y = 0;
    for (; first != last; ++ first) {
        int x = *first;
        assert (last_x <= x);
        last_x = x;
        if (y < x) break;
        if (y == x) ++ y;
    }
    return y;
}

Back to top page