全ての非負整数 \(x\) について以下が成り立ちます。
\(MEX\) を \(x+1\) 以上にするには \(x\) を \(B\) の要素として選ぶ必要があります。逆に、要素が重複しても \(MEX\) には影響しないため、 \(x\) を \(2\) つ以上選ぶメリットはありません。

このことから、次のアルゴリズムが成立する。

• \(i=0,1,\dots,K-1\) まで、以下を繰り返す。
  • もし \(A\) に \(i\) が含まれる場合、それを選び出す。これにより、答えが \(i+1\) 以上となることが確定する。
  • そうでない場合、 \(MEX\) の値を \(i\) より大きくすることはできないため、答えが \(i\) であると判明して終了する。
• 上記が終了しても答えが判明しなかった場合、 \(B\) を \((0,1,\dots,K-1)\) の並べ替えとすることができているので、答えは \(K\) である。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,k;
  cin >> n >> k;
  set<int> st;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    st.insert(a);
  }
  for(int i=0;i<k;i++){
    if(st.find(i)==st.end()){
      cout << i << "\n";
      return 0;
    }
  }
  cout << k << "\n";
  return 0;
}