Prerequisite : - Hashing, Maps, Sorting
Problem :- There are three lists storing the ids of voters, some voters may repeat in these lists.
Find the number of voters which are present in more than one list and their ids.
Explanation :- The problem can be solved using different logic. Here, we discuss two types of implementation: first, using hashing/Map, and second, using sorting techniques.
Logic1
Using hashing will help us solve this problem. It is a data structure that allows us to store data in the form of key-value pairs, enabling us to track the frequency of each ID. We can assign each ID as a key and initialize its corresponding value as 0. Then, we can follow the steps to achieve our goal.
Iterate over each list.
Access each id in the list and update its frequency in the map.
Iterate over all the elements of the map and store the element with frequency more than 1.
Print the count of elements, and all the elements with frequency more than 1.
Logic2
Sorting can solve this problem. Once the array is sorted, all similar elements will get grouped together, allowing one to count each element. If the count of any element is 2 or more, it should be stored in an array. Then, we can print the number of elements stored in the array and the elements themselves.
C++ Solution : -
Using Hashing technique
#include <bits/stdc++.h>
using namespace std;
int main() {
map<int,int>m1;
int n,m,k;
cin>>n>>m>>k;
for(int i=0; i < n+m+k; i++){
int n1;
cin>>n1;
m1[n1]++;
}
vector<int>ans;
for(auto e:m1){
if(e.second>1){
ans.push_back(e.first);
}
}
cout<<ans.size()<<"\n";
for(auto e:ans){
cout<<e<<"\n";
}
}
Using Sorting technique
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m,k;
cin>>n>>m>>k;
vector<int>v1;
for(int i=0; i < n+m+k; i++){
int n1;
cin>>n1;
v1.push_back(n1);
}
sort(v1.begin(),v1.end());
int cnt = 1;
vector<int>ans;
for(int i=1;i<n+k+m;i++)
{
if(v1[i]==v1[i-1]){
cnt = cnt + 1;
}
else{
cnt = 1;
}
if(cnt == 2){
ans.push_back(v1[i]);
// cout<<v1[i]<<"\n";
}
}
cout<<ans.size()<<"\n";
for(auto e:ans)
{
cout<<e<<"\n";
}
}