ECAPR204 - Editorial

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;
}
3 Likes