PROBLEM LINK:
Practice
Encoding April’20 Contest
Author: shrivas7
Tester: dshahid380_
Editorialist: shrivas7
DIFFICULTY:
EASY
PREREQUISITES:
MAP, HASHING
EXPLANATION:
The main idea is to treat the Data Values as keys and increment the value with the occurence. But since the constrains are large, Array cannot be used to hash the data. Thus we use map where key(long long) is data value and its value is frequency. After the creation of the hash table ,it is iterated using an iterator to print the result.
TIME COMPLEXITY:
O(N+M) ,where M is no. of distinct data values.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
ll t,n,i,s;
cin>>t;
while(t--)
{
map<ll ,ll> m;
cin>>n;
for(i=0;i<n;i++)
{
cin>>s;
m[s]++;
}
map<ll, ll>::iterator itr;
for (itr=m.begin();itr!=m.end();itr++)
cout<< itr->first <<":"<<itr->second <<endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long int
#define ll long long int
#define vi vector<int>
#define vvi vector<vector<int>>
#define pll pair<ll, ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vpll vector<pair<ll,ll>>
#define umap unordered_map
#define uset unordered_set
#define all(c) c.begin(), c.end()
#define maxarr(A) *max_element(A, A+n)
#define maxvec(v) *max_element(all(v))
#define present(map,elem) map.find(elem)!=map.end()
#define lb(v,elem) lower_bound(all(v),elem)
#define ub(v,elem) upper_bound(all(v),elem)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define For(i,a,b) for(int i=a; i<b; ++i)
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define debug(v) for(ll i=0; i<v.size(); i++) cout<<v[i]<<" "; cout<<endl;
#define debugn(v,n) for(ll i=0; i<n; i++) cout<<v[i]<<" "; cout<<endl;
#define mod 1000000007
#define endl '\n'
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("1.in","r",stdin);
int t;
cin>>t;
assert(t<=10);
while(t--){
ll n;
cin>>n;
assert(n<=100000 && n>1);
umap<ll,ll> d;
vl v;
for(ll i=0; i<n; i++){
ll x;
cin>>x;
assert(x>=1 && x<=(ll)1e18);
if(d.find(x)==d.end()){
v.pb(x);
}
d[x]++;
}
sort(all(v));
for(ll u : v){
cout<<u<<":"<<d[u]<<endl;
}
}
return 0;
}