PROBLEM LINK:
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.