ELOCUTE-EDITORIAL

editorial
, ,
1

Practice

Contest

Author: Mrudula Kulkarni

Tester: Mrudula Kulkarni

Editorialist: Mrudula Kulkarni

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation

PROBLEM:

You are given two integers N and M denoting the total number of speakers and a total number of topics respectively. You are also given an array A where Ai denotes the topic on which ith speaker is going to speak on.

You need to tell whether Neha can win a prize this year. Neha wins the prize if she chooses a unique topic.

EXPLANATION :

Since criteria for winning the competition is to choose a unique topic. Hence we just need to find a topic that hasn’t been selected by any of the speakers.

So the main idea is to find the distinct elements in the array. So to find the distinct elements in  O(N log N) , we need to use sorting. The array is sorted so that all occurrences of every element become consecutive. Once the occurrences become consecutive, we can traverse the sorted array and count distinct elements in O(n) time.

SOLUTION :

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
void solve(){
       int n,m,d=0;
       cin>>n>>m;
       int arr[n];
       for(int i=0;i<n;i++){
              cin>>arr[i];
         }
      sort(arr,arr+n);
      for(int j=0;j<n;j++){
            if(j==n-1){
               d++;
            }
           else if(arr[j]!=arr[j+1]){
                 d++;
           }
      }
      if(d<m){
            cout<<"Yes"<<endl;
        }
     else{
            cout<<"No"<<endl;
        }
}
int main(){
     int t;
     cin>>t;
     while(t--){
         solve();
   }
}