KMEX - Editorial

editorial
,
1

PROBLEM LINK:

Contest
Practice

Setter: soumyadeep_21
Testers: gamegame

DIFFICULTY:

1450

PREREQUISITES:

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;
}