 # PROBLEM LINK:

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

EASY

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;
}
``````
1 Like