Find the Number of Maximum Product Quadruples | Python3 program to find the number of Quadruples having maximum product ; Returns the number of ways to select r objects out of available n choices ; ncr = ( n * ( n - 1 ) * ( n - 2 ) * ... . . ... ( n - r + 1 ) ) / ( r * ( r - 1 ) * ... * 1 ) ; Returns the number of quadruples having maximum product ; stores the frequency of each element ; remaining_choices denotes the remaining elements to select inorder to form quadruple ; traverse the elements of the map in reverse order ; If Frequency of element < remaining choices , select all of these elements , else select only the number of elements required ; Decrement remaining_choices acc to the number of the current elements selected ; if the quadruple is formed stop the algorithm ; Driver Code
from collections import defaultdict NEW_LINE def NCR ( n , r ) : NEW_LINE INDENT numerator = 1 NEW_LINE denominator = 1 NEW_LINE while ( r > 0 ) : NEW_LINE INDENT numerator *= n NEW_LINE denominator *= r NEW_LINE n -= 1 NEW_LINE r -= 1 NEW_LINE DEDENT return ( numerator // denominator ) NEW_LINE DEDENT def findWays ( arr , n ) : NEW_LINE INDENT count = defaultdict ( int ) NEW_LINE if ( n < 4 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT count [ arr [ i ] ] += 1 NEW_LINE DEDENT remaining_choices = 4 NEW_LINE ans = 1 NEW_LINE for it in reversed ( sorted ( count . keys ( ) ) ) : NEW_LINE INDENT number = it NEW_LINE frequency = count [ it ] NEW_LINE toSelect = min ( remaining_choices , frequency ) NEW_LINE ans = ans * NCR ( frequency , toSelect ) NEW_LINE remaining_choices -= toSelect NEW_LINE if ( not remaining_choices ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 3 , 3 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE maxQuadrupleWays = findWays ( arr , n ) NEW_LINE print ( maxQuadrupleWays ) NEW_LINE DEDENT