CCAKES - Editorial

editorial
,
1

PROBLEM LINK

Practice

Contest Link

Problem Setter : Rounak Neogy
Editorialist: Kanist Agarwal

DIFFICULTY

Easy

PREREQUISITES:

Basic observations, application of map.

PROBLEM:

Given an array A of N cakes , where A_i , 1 \le i \le N represents the flavour of the i^{th} cake .You are required to print that flavour of cake which has the highest frequency and is maximum in value.

EXPLANATION

In the given problem we just need to find the frequency of all the flavours using a map.
STL ordered map is recommended in this problem (For C++ users) because
max(A_i ) \le 10^9 . So using an unordered map is not suggested because it might lead to collisions and you can end up getting a wrong answer. Well that can be fixed too but still using map here is perfectly fine here.

The time complexity of the solution will be O(NlogN) because insertion in map is O(logN).

Space complexity : O(N)

SOLUTIONS :

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
 
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
 
    map<int,int> mp;
 
    for(int i=0;i<n;i++){
        mp[arr[i]]++;
    }
   
    int maxCount=0,maxFlavour=INT_MIN;
    for(auto itr:mp){
        if(itr.second==maxCount){
            maxCount=itr.second;
            maxFlavour=max(maxFlavour,itr.first);
        }
        else if(itr.second>maxCount){
            maxCount=itr.second;
            maxFlavour=itr.first;
        }
    }
 
    cout<<maxFlavour<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
Editorialist's Solution 
#include <bits/stdc++.h>
#define ull unsigned ll
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pi acos(-1)
#define INF 1e14
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define F(i,a,n) for(int i=a;i<n;i++)
#define vll vector<ll>
using namespace std;

int main()
{

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tt;
    tt = 1;
    cin >> tt;
    while (tt--)
    {
        ll maxi = 0;
        ll n;
        cin >> n;
        vll a(n);
        map<ll, ll>m;
        F(i, 0, n)
        {
            cin >> a[i];
            m[a[i]]++;
        }
        ll p = 0;
        for (auto i : m)
        {
            if (i.ss >= p)
            {
                p = i.ss;
                if (maxi < i.ff)
                {
                    maxi = i.ff;
                }
            }
        }
        cout << maxi << "\n";

    }
    return 0;

}