Maximum number of pairs of distinct array elements possible by including each element in only one pair | C ++ program for the above approach ; Function to count the maximum number of pairs having different element from the given array ; Stores the frequency of array element ; Stores maximum count of pairs ; Increasing the frequency of every element ; Stores the frequencies of array element from highest to lowest ; Pushing the frequencies to the priority queue ; Iterate until size of PQ > 1 ; Stores the top two element ; Form the pair between the top two pairs ; Decrement the frequencies ; Insert updated frequencies if it is greater than 0 ; Return the total count of resultant pairs ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumPairs ( int a [ ] , int n ) { map < int , int > freq ; int count = 0 ; for ( int i = 0 ; i < n ; ++ i ) freq [ a [ i ] ] ++ ; priority_queue < int > pq ; for ( auto itr = freq . begin ( ) ; itr != freq . end ( ) ; itr ++ ) { pq . push ( itr -> second ) ; } while ( pq . size ( ) > 1 ) { int freq1 = pq . top ( ) ; pq . pop ( ) ; int freq2 = pq . top ( ) ; pq . pop ( ) ; count ++ ; freq1 -- ; freq2 -- ; if ( freq1 > 0 ) pq . push ( freq1 ) ; if ( freq2 > 0 ) pq . push ( freq2 ) ; } return count ; } int main ( ) { int arr [ ] = { 4 , 2 , 4 , 1 , 4 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximumPairs ( arr , N ) ; return 0 ; }