Minimum Excluded Value (MEX)

Mex kind of scares me. I need to write down the common ideas associated with this.

Codeforces problems:

• TODO: add here the ones I did
• https://codeforces.com/contest/2003/problem/D1
• And D2

Resources

• https://cp-algorithms.com/sequences/mex.html
• 3 Approaches to Calculating the Mex of an Array (has -10 downvote)

I have bottleneck when computing MEX

• https://codeforces.com/contest/2003/problem/D2

int mex(vector<int> &a) {
    vector<bool> f(a.size() + 1, 0);
    for (int i : a) if (i <= (int) a.size()) f[i] = 1;
    int mex = 0;
    while (f[mex]) ++mex;
    return mex;
}