Maximum number of pairs of distinct array elements possible by including each element in only one pair |  ; stores the frequency array ; maxi stores the maximum frequency of an element ; it stores the sum of all the frequency other than the element which has maximum frequency ; there will be always zero or more element which will not participate in making pairs ; if n is odd then except one element we can always form pair for every element if n is even then all the elements can form pair
#include <bits/stdc++.h> NEW_LINE using namespace std ; int main ( ) { int arr [ ] = { 4 , 2 , 4 , 1 , 4 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int maxi = 0 , remain , ans ; map < int , int > freq ; for ( int i = 0 ; i < n ; i ++ ) { freq [ arr [ i ] ] ++ ; } for ( auto it : freq ) { maxi = max ( maxi , it . second ) ; } remain = n - maxi ; if ( maxi >= remain ) { ans = remain ; } else { ans = n / 2 ; } cout << ans ; freq . clear ( ) ; return 0 ; }