maximal product of quadruplets

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