Given an array A[] of integers. The task is to display the ordered pairs of
positive integers (X, Y) such that X occurs in A[] at least Y times
and Y occurs in A at least X times
e.g.input A[] = { 1, 1, 2, 2, 3 } -- the program runs fine with this input.
Ordered pairs are -> { [1, 1], [1, 2], [2, 1], [2, 2] }
e.g. Input : A = { 3, 3, 2, 2, 2 } -- the program crashes with segmentation fault with this
Ordered pairs are -> { [3, 2], [2, 2], [2, 3] }
In function getDesiredSet(), at the below lines, the find fails with segmentation error.
it1 = freqMap.find(itr->first);
it2 = freqMap.find(itr->second);
# include "iostream"
# include "map"
# include "iterator"
# include "set"
using namespace std;
typedef pair<int, int> pairs;
map<int,int> getFreqMap(int arr[], int n){
map<int,int> freqMap;
map<int, int>::iterator it;
for (int i=0; i<n; i++){
//if( freqMap.find(arr[i]) != freqMap.end()){
if (freqMap.count(arr[i])){
it = freqMap.find(arr[i]);
it->second = freqMap.count(arr[i]) + 1;
freqMap[arr[i]] = freqMap.count(arr[i]) +1;
}
else{
freqMap.insert(pair<int,int> (arr[i], 1) );
}
}
cout << "\nFrequency Map - Element : Freq\n";
for (it = freqMap.begin(); it!= freqMap.end(); it++){
cout << it->first << " : " << it->second << endl;
}
return freqMap;
}
/* getPairSet finds out all the possible ordered pairs with the input numbers*/
/* and stores them in a set(so that there are no repeatation) */
set<pair<int,int> > getPairSet(int arr[], int n){
set <pairs> s;//setOfPairs ;
for (int i=0; i<n; i++){
for (int j=0; j<n-1; j++){
pairs p = make_pair(arr[i],arr[j]);
s.insert(p);
}
}
set< pairs >:: iterator itr;
cout << "\nPossible Pairs out of the given numbers in the array:\n";
for (itr = s.begin(); itr != s.end(); itr++){
cout <<"(" <<(*itr).first << "," << (*itr).second <<") " ;
}
return s;
}
/* getDesiredSet removes those order pairs which do match the criteria*/
/* in other words, it removes those order pairs in which */
/* either the frequency of 1st item is less than 2nd item */
/* or frequency of 2nd item is less than 1st item */
set<pairs > getDesiredSet(set<pairs > pairSet, map<int, int> freqMap){
set<pairs > ::iterator itr, itrEnd;
map<int, int>:: iterator it1, it2;
for (itr = pairSet.begin(); itr != pairSet.end(); itr++){
it1 = freqMap.find(itr->first);
it2 = freqMap.find(itr->second);
if ((it1->second < itr->second) || (it2->second < itr->first)){
itrEnd = itr;
std::advance(itrEnd , 1);
pairSet.erase(itr, itrEnd);
}
}
return pairSet;
}
int main(){
map<int, int> freqMap;
int arr[] = { 3, 3, 2, 2, 2 };
cout << "\nInput Array Elements:\n";
int n = sizeof(arr)/sizeof(arr[0]);
for (int z=0; z< n; z++)
cout << arr[z] << " ";
freqMap = getFreqMap(arr, n);
set<pair<int,int> > pairSet = getPairSet(arr,n);
set<pair<int,int> > desiredSet = getDesiredSet(pairSet, freqMap);
set<pair<int,int> > :: iterator itr;
cout << "\n\nDesired order pairs\n";
for (itr = desiredSet.begin(); itr != desiredSet.end(); itr++){
cout <<"(" <<(*itr).first << "," << (*itr).second <<") " ;
}
return 0;
}
