# KMEX - Editorial

Testers: gamegame

1450

None

# PROBLEM:

Given an array with N integers. Find if you can select M elements from it, whose MEX is K.

# EXPLANATION:

We need to check three points:

• Does the array have M elements which are not K?
• Does the array have at least 1 element whose value is i, for every 0 \le i \lt K?
• Is M large enough so that all these values from 0 to K-1 can be selected?

If the answer to all these 3 points is Yes, then the final answer is Yes. Even if one of them is No, the final answer is No.

# TIME COMPLEXITY:

Time complexity is O(N).

# SOLUTION:

Editorialist's Solution
``````#include <iostream>
using namespace std;

int t, n, m, k, a, Freq[101];

int main() {

cin>>t;

while(t--)
{
cin>>n>>m>>k;

int notk=0;
for(int i=0;i<=n;i++)
Freq[i]=0;

for(int i=1;i<=n;i++)
{
cin>>a;
if(a!=k)
notk++;
Freq[a]++;
}

if((notk<m)||(m<k))
{
cout<<"no\n";
continue;
}

int poss = 1;
for (int i=0;i<k;i++)
{
if(Freq[i]==0)
{
poss=0;
break;
}
}

if(poss==0)
{
cout<<"no\n";
}
else
{
cout<<"yes\n";
}

}

return 0;
}
``````
Tester's Solution
``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=1e9+7;
int n,m,k;
int f[501];
void solve(){
cin >> n >> m >> k;
for(int i=0; i<=n ;i++) f[i]=0;
for(int i=1; i<=n ;i++){
int x;cin >> x;f[x]++;
}
for(int i=0; i<k ;i++){
if(f[i]==0){
cout << "NO\n";
return;
}
}
if(m+f[k]>n || m<k) cout << "NO\n";
else cout << "YES\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}
``````
Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m, k;
cin >> n >> m >> k;
vector<int> fre(n + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
fre[x]++;
}
bool flag = (m >= k) && (n - fre[k] >= m);
for (int i = 0; i < k; i++) {
flag &= (fre[i] > 0);
}
if (flag) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}
``````