Contest Duration: - (local time) (100 minutes) Back to Home
Official

## B - Mex Editorial by en_translator

Since $$0,1,\ldots,N$$ has $$N+1$$ integers, the upper bound of the answer is $$N$$.

For each $$ans=0,1,2,\ldots,N$$, solve the following problem:

Does $$A$$ contains $$ans$$?

Once an integer that does not contained in $$A$$ for the first time, we can determine that that is the answer.

The time complexity is $$O(N^2)$$.

With a boolean array, the problem can also be solved in a total of $$O(N)$$ too.

Sample code in $$O(N^2)$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main(){
ll n;cin>>n;
vector<ll>a(n);
for(ll i=0;i<=n-1;i++)cin>>a[i];
for(ll ans=0;ans<=n;ans++){
bool ok=true;
for(ll x:a){
if(x==ans)ok=false;
}
if(ok){
cout<<ans<<endl;
return 0;
}
}
return 0;
}


posted:
last update: