MODEFREQ - Editorial

PROBLEM LINK:

Practice
Contest

Setter: Akash Bhalotia
Tester: Yash Chandnani
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Cakewalk

PREREQUISITES:

Frequency Array and Ad-hoc.

PROBLEM:

You are given N numbers ranging from 1 to 10. You have to compute the mode of the frequencies of the numbers present in the array. If there are multiple frequencies with the same frequency output the smallest one.

EXPLANATION:

First, you have to compute the number of occurrence(frequency) of number ranging from 1 to 10 present in the array this can be done using frequency array. To avoid confusion let us refer to the frequency of the number i as B_i. Now we have to find the mode of array B(note we don’t have to consider B_i, which is equal to 0 as these elements are not present in the original array). Now to find the number of occurrence(frequency) of number present in B using frequency array(note the magnitude of B_i can reach upto 10,000 as maximum value of N is 10,000 so we will make a frequency array for B till 10,000). And the maximum value in the frequency array of B will be our answer. In the case of repeated maximum values in the frequency array take the smallest B_i for which frequency is maximum.

TIME COMPLEXITY:

  • O(N) per test case.

SOLUTIONS:

Setter's Solution
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N;

        int T=Integer.parseInt(br.readLine().trim());
        StringBuilder sb=new StringBuilder();

        while(T-->0)
        {
            N=Integer.parseInt(br.readLine().trim());
            int a[]=new int[N];
            String[] s=br.readLine().trim().split(" ");
            for(i=0;i<N;i++) a[i]=Integer.parseInt(s[i]);

            int[] freq=new int[11]; //To find the frequency of numbers
            int[] freqOfFreq=new int[N+1]; //To find the frequency of frequencies

            for(i=0;i<N;i++) freq[a[i]]++;
            for(i=1;i<=10;i++) freqOfFreq[freq[i]]++;

            int ans=1,max=freqOfFreq[1];
            for(i=2;i<=N;i++) //Finding the mode
            {
                if(freqOfFreq[i]>max)
                {
                    max=freqOfFreq[i];
                    ans=i;
                }
            }
            sb.append(ans).append("\n");
        }
        System.out.println(sb);
    }
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
void pre(){
 
 
}
int cnt[11];
int a[10009];
void solve(){
	int n = readIntLn(1,10000);
	rep(i,n-1){
		a[i] = readIntSp(1,10);
	}
	a[n-1] = readIntLn(1,10);
	fill(cnt);
	rep(i,n) cnt[a[i]]++;
	map<int,int> m;
	repA(i,1,10) if(cnt[i])	{
		m[cnt[i]]++;
	}
	int ans = 0,mx=0;
	trav(i,m) if(i.snd>mx) mx=i.snd,ans=i.fst;
	cout<<ans<<'\n';
 
 
}
 
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	int n=readIntLn(1,100);
	rep(i,n) solve();
	assert(getchar()==EOF);
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

void solveTestCase() {
	int N;
	cin >> N;
	vector<int> freq(11, 0);
	for(int i = 0; i < N; i ++) {
		int in;
		cin >> in;
		freq[in] ++;
	}
	vector<int> freq_of_freq(10001, 0);
	for(int i = 1; i <= 10; i ++) {
		if(freq[i]) {
			freq_of_freq[freq[i]] ++;
		}
	}
	int maxFreq = 0, id = -1;
	for(int i = 1; i <= 10000; i ++) {
		if(freq_of_freq[i] > maxFreq) {
			maxFreq = freq_of_freq[i];
			id = i;
		}
	}
	cout << id << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int testCase;
	cin >> testCase;
	for(int i = 1; i <= testCase; i ++) {
		solveTestCase();
	}

	return 0;
}

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

5 Likes

can you help me? I don’t know why my code is rejected. I have tried my own test cases as well. It works fine for me.
https://www.codechef.com/viewsolution/37600993

It was not working for some of the test cases anyone please look into it

what’s the problem in my code ?? it gives TLE.
#include<bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t; cin>>t;
while(t–){
int n; cin>>n;
int a; int hsh[10];
for(int i=0;i<n;i++){
cin>>a;
hsh[a]++;
}
int Max=0;
int ct=0, res=0;
for(int i=1;i<=10;i++){
for(int j=i+1;j<=10;j++){
if(hsh[j]>0){
if(hsh[i]==hsh[j]) {ct++; hsh[j]=-1;}
}}
if(Max<ct){ Max=ct; res=hsh[i];}
else if(Max==ct){if(hsh[i]<res) res=hsh[i];}
}
cout<<res<<endl;
}
return 0;
}