CANDYTYPE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: raysh07

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N candies, with colours A_1, A_2, \ldots, A_N. What is the most frequent colour among the candies? In case of tie, print the smallest colour.

EXPLANATION:

We can calculate a frequency array f_x = the number of times x appears in the A. Then, we simply find the index of the maximum element in this array.

The frequency array can be created as follows:

let f = [0, 0, ....0] // n + 1 sized array of 0s
for x in A:
f[x] += 1

Then, the maximum element can be found as follows:

best = 1
for i = 1 to N:
if f[i] > f[best]: best = i

This psuedocode also ensures we choose the smallest in case of ties because we only change when its strictly larger.

TIME COMPLEXITY:

\mathcal{O}(n) per testcase.

CODE:

Editorialist's Code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> a(n);
    for (auto &x : a) cin >> x;
    
    vector <int> f(n + 1, 0);
    for (auto x : a) f[x]++;
    
    int best = 1;
    for (int i = 2; i <= n; i++) if (f[i] > f[best]) best = i;
    cout << best << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}