POPPUSH1 - Editorial

PROBLEM LINK:

Practice
Contest-Link

Author: Yash Dwivedi
Tester: Anuranjan Srivastava
Editorialist: Anuranjan Srivastava

DIFFICULTY:

EASY

PREREQUISITES:

Hashing

PROBLEM:

You are given an array C of n integers where -10^3 <= Ci <= 10^3 and 1 <= n <= 10^4. Here Ci will represent the type of sweet. The constraint is that you can only choose one type of sweet in a day and reduce it atmost by 2. you have to find out the minimum number of days it will take to finish the sweets.

QUICK EXPLANATION:

Count the frequency of each Ci in a map and just check how many days it took to finish all sweets of that type. Do this for every type and add the number of days for each.

EXPLANATION:

From the problem statement, it is clear that we need to think of a greedy solution. Firstly we need to count the frequency of all the types of Ci in a map or an array. If a particular type of Ci is present more than once then we need to eat two sweets of that type in a day and if still one sweet remains then we need one additional day to eat that sweet. In the same way, we will do the counting for all the sweets.

SOLUTIONS:

Setter's Solution
    #include  <bits/stdc++.h>
    using namespace std;
    #define ll long long 
    int main()
    {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int t=1; 
    //cin>>t;
    while(t--)
     {
     ll n,i;
    cin>>n;
    map<ll,ll>mp;
    for(i=0;i<n;i++;)
    {
    ll x;
    cin>>x;
    mp[x]++;
     }
    ll s=0;
    for(auto i:mp)
    s+=i.second/2+i.second%2;
    cout<<s<<"\n";
    }
    return 0;
    }
Tester's Solution
#include  <bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 int n;
 cin>> n;
vector<int> a(n, 0);
for (int i = 0; i < n; i++)
cin>> a[i];
map<int, int> m;
for (int i = 0; i < n; i++)
m[a[i]]++;
map<int, int>::iterator it;
int ans = 0;
for (it = m.begin(); it != m.end(); it++)
{
if (it->second % 2 != 0)
ans += 1;
ans += (it->second / 2);
}
cout<< ans <<"\n";
return 0;
}
Editorialist's Solution
#include  <bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 int n;
 cin>> n;
vector<int> a(n, 0);
for (int i = 0; i < n; i++)
cin>> a[i];
map<int, int> m;
for (int i = 0; i < n; i++)
m[a[i]]++;
map<int, int>::iterator it;
int ans = 0;
for (it = m.begin(); it != m.end(); it++)
{
if (it->second % 2 != 0)
ans += 1;
ans += (it->second / 2);
}
cout<< ans <<"\n";
return 0;
}