Official
D - 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: