Maximum number of unique Triplets such that each element is selected only once | C ++ program for the above approach ; Function that finds maximum number of triplets with different elements ; Map M will store the frequency of each element in the array ; Priority queue of pairs { frequency , value } ; ans will store possible triplets ; Extract top 3 elements ; Make a triplet ; Decrease frequency and push back into priority queue if non - zero frequency ; Print the triplets ; Print the triplets ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findTriplets ( int ar [ ] , int n ) { unordered_map < int , int > mp ; for ( int x = 0 ; x < n ; x ++ ) mp [ ar [ x ] ] ++ ; priority_queue < pair < int , int > > pq ; for ( auto & pa : mp ) pq . push ( { pa . second , pa . first } ) ; vector < array < int , 3 > > ans ; while ( pq . size ( ) >= 3 ) { pair < int , int > ar [ 3 ] ; for ( int x = 0 ; x < 3 ; x ++ ) { ar [ x ] = pq . top ( ) ; pq . pop ( ) ; } ans . push_back ( { ar [ 0 ] . second , ar [ 1 ] . second , ar [ 2 ] . second } ) ; for ( int x = 0 ; x < 3 ; x ++ ) { ar [ x ] . first -- ; if ( ar [ x ] . first ) pq . push ( ar [ x ] ) ; } } cout << " Maximum ▁ number ▁ of ▁ " << " possible ▁ triples : ▁ " ; cout << ans . size ( ) << endl ; for ( auto & pa : ans ) { for ( int v : pa ) cout << v << " ▁ " ; cout << endl ; } } int main ( ) { int arr [ ] = { 2 , 2 , 3 , 3 , 4 , 4 , 4 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findTriplets ( arr , n ) ; return 0 ; }