Ways to form n / 2 pairs such that difference of pairs is minimum | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define mp  make_pair NEW_LINE #define pb  push_back NEW_LINE #define S  second NEW_LINE #define ll  long long NEW_LINE using namespace std ; const int mod = 1000000007 ; const int MAX = 100000 ; ll ways [ MAX + 1 ] ; void preCompute ( ) { ways [ 0 ] = 1LL ; ways [ 2 ] = 1LL ; for ( int i = 4 ; i <= MAX ; i += 2 ) { ways [ i ] = ( 1LL * ( i - 1 ) * ways [ i - 2 ] ) % mod ; } } void countWays ( int * arr , int n ) { map < int , int > count ; for ( int i = 0 ; i < n ; i ++ ) count [ arr [ i ] ] ++ ; vector < pair < int , int > > count_vector ; map < int , int > :: iterator it ; for ( it = count . begin ( ) ; it != count . end ( ) ; it ++ ) { count_vector . pb ( mp ( it -> first , it -> second ) ) ; } sort ( count_vector . begin ( ) , count_vector . end ( ) ) ; ll ans = 1 ; for ( int i = count_vector . size ( ) - 1 ; i > 0 ; i -- ) { int current_count = count_vector [ i ] . S ; int prev_count = count_vector [ i - 1 ] . S ; if ( current_count & 1 ) { ans = ( ans * ways [ current_count - 1 ] ) % mod ; ans = ( ans * current_count ) % mod ; ans = ( ans * prev_count ) % mod ; if ( prev_count & 1 ) { ans = ( ans * ways [ prev_count - 1 ] ) % mod ; count_vector [ i - 1 ] . S = 0 ; } else { count_vector [ i - 1 ] . S -- ; } } else { ans = ( ans * ways [ current_count ] ) % mod ; } } ans = ( ans * ways [ count_vector [ 0 ] . S ] ) % mod ; cout << ans << " STRNEWLINE " ; } int main ( ) { preCompute ( ) ; int arr [ ] = { 2 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; countWays ( arr , n ) ; return 0 ; }