Ways to form n / 2 pairs such that difference of pairs is minimum | Python3 implementation of the above approach ; Using mod because the number of ways might be very large ; ways is serving the same purpose as discussed ; pairing up zero people requires one way . ; map count stores count of s . ; sort according to value ; Iterating backwards . ; Checking if current count is odd . ; if current count = 5 , multiply ans by ways [ 4 ] . ; left out person will be selected in current_count ways ; left out person will pair with previous person in previous_count ways ; if previous count is odd , then multiply answer by ways [ prev_count - 1 ] . since one has already been reserved , remaining will be even . reduce prev_count = 0 , since we don 't need it now. ; if prev count is even , one will be reserved , therefore decrement by 1. In the next iteration , prev_count will become odd and it will be handled in the same way . ; if current count is even , then simply multiply ways [ current_count ] to answer . ; multiply answer by ways [ first__count ] since that is left out , after iterating the array . ; Driver code
from collections import defaultdict NEW_LINE mod = 1000000007 NEW_LINE MAX = 100000 NEW_LINE ways = [ None ] * ( MAX + 1 ) NEW_LINE def preCompute ( ) : NEW_LINE INDENT ways [ 0 ] = 1 NEW_LINE ways [ 2 ] = 1 NEW_LINE for i in range ( 4 , MAX + 1 , 2 ) : NEW_LINE INDENT ways [ i ] = ( ( 1 * ( i - 1 ) * ways [ i - 2 ] ) % mod ) NEW_LINE DEDENT DEDENT def countWays ( arr , n ) : NEW_LINE INDENT count = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT count [ arr [ i ] ] += 1 NEW_LINE DEDENT count_vector = [ ] NEW_LINE for key in count : NEW_LINE INDENT count_vector . append ( [ key , count [ key ] ] ) NEW_LINE DEDENT count_vector . sort ( ) NEW_LINE ans = 1 NEW_LINE for i in range ( len ( count_vector ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT current_count = count_vector [ i ] [ 1 ] NEW_LINE prev_count = count_vector [ i - 1 ] [ 1 ] NEW_LINE if current_count & 1 : NEW_LINE INDENT ans = ( ans * ways [ current_count - 1 ] ) % mod NEW_LINE ans = ( ans * current_count ) % mod NEW_LINE ans = ( ans * prev_count ) % mod NEW_LINE if prev_count & 1 : NEW_LINE INDENT ans = ( ans * ways [ prev_count - 1 ] ) % mod NEW_LINE count_vector [ i - 1 ] [ 1 ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT count_vector [ i - 1 ] [ 1 ] -= 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT ans = ( ans * ways [ current_count ] ) % mod NEW_LINE DEDENT DEDENT ans = ( ans * ways [ count_vector [ 0 ] [ 1 ] ] ) % mod NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT preCompute ( ) NEW_LINE arr = [ 2 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE countWays ( arr , n ) NEW_LINE DEDENT