Maximum number of pairs of distinct array elements possible by including each element in only one pair | 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
def maximumPairs ( a , n ) : NEW_LINE INDENT freq = { } NEW_LINE count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if a [ i ] in freq : NEW_LINE INDENT freq [ a [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT freq [ a [ i ] ] = 1 NEW_LINE DEDENT DEDENT pq = [ ] NEW_LINE for key , value in freq . items ( ) : NEW_LINE INDENT pq . append ( value ) NEW_LINE DEDENT pq . sort ( ) NEW_LINE while ( len ( pq ) > 1 ) : NEW_LINE INDENT freq1 = pq [ len ( pq ) - 1 ] NEW_LINE pq = pq [ : - 1 ] NEW_LINE freq2 = pq [ len ( pq ) - 1 ] NEW_LINE pq = pq [ : - 1 ] NEW_LINE count += 1 NEW_LINE freq1 -= 1 NEW_LINE freq2 -= 1 NEW_LINE if ( freq1 > 0 ) : NEW_LINE INDENT pq . append ( freq1 ) NEW_LINE DEDENT if ( freq2 > 0 ) : NEW_LINE INDENT pq . append ( freq2 ) NEW_LINE DEDENT pq . sort ( ) NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , 2 , 4 , 1 , 4 , 3 ] NEW_LINE N = len ( arr ) NEW_LINE print ( maximumPairs ( arr , N ) ) NEW_LINE DEDENT