Count pairs (p, q) such that p occurs in array at least q times and q occurs at least p times in C++

We are given an array of positive integers. The goal is to find the count of pairs of elements of arr[] such that pairs have elements ( p, q ) where p occurs in array for at least q times and q occurs in array for at-least p times.

Let us understand with examples.

Input − int arr[] = { 3, 3, 3, 5, 5, 6, 6}

Output − Count of pairs in an array such that frequency of one is at least value of other are − 1

Explanation − The valid pairs in an array where p occurs q times and q occurs p times are (3, 3) as 3 is occurring 3 times in an array. So there is only one valid pair hence the count is 1.

Input − int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6}

Output − Count of pairs in an array such that frequency of one is at least value of other are − 1

Explanation − The valid pairs in an array where p occurs q times and q occurs p times are (3, 3), (5, 5) and (3, 5) as 3 is occurring 5 times and 5 is occurring 3 times in an array. So there are three valid pairs hence the count is 3.

Approach used in the below program is as follows

• Input an array of integer elements and calculate the size of an array and pass the data to the function for further processing

• Declare a temporary variable count to store the occurrences of p and q

• Create a variable vec of type vector and um of type unordered_map

• Start loop FOR from 0 till the size of an array

• Inside the loop, set um[arr[i]] by 1 and check IF the um is 1 then push arr[i] in the vector

• Start another loop FOR from 0 till the size of a vector and check IF um[vec[i] < vec[i] then continue, ELSE IF they are equal then increment the count by 1 ELSE increment the count by 1. Start another loop j FOR from j to vec[i] + 1 till um[vec[i]].

• Inside the loop j check IF um[j] >= vec[i] then increment the count by 1

• Return the count

• Print the result.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int pair_count(int arr[], int len){    int count = 0;    vector<int> vec;    unordered_map<int, int> um;    for (int i = 0; i < len; i++){       um[arr[i]]++;       if (um[arr[i]] == 1){          vec.push_back(arr[i]);       }    }    for (int i = 0; i < vec.size(); i++){       if (um[vec[i]] < vec[i]){          continue;       }       else if (um[vec[i]] == vec[i]){          count++;;       }       else{          count++;          for (int j = vec[i] + 1; j <= um[vec[i]]; j++){             if (um[j] >= vec[i]){                count++;             }          }       }    }    return count; } int main(){    int arr[] = { 1, 1, 1, 5, 5, 1};    int size = sizeof(arr) / sizeof(arr[0]);    cout<<"Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: "<<pair_count(arr, size);    return 0; }

Output

If we run the above code it will generate the following output −

Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1