Count number of subsets whose median is also present in the same subset | Python 3 implementation of the approach ; Function to return the factorial of a number ; Function to return the value of nCr ; Function to return ' a ' raised to the power n with complexity O ( log ( n ) ) ; Function to return the number of sub - sets whose median is also present in the set ; Number of odd length sub - sets ; Sort the array ; Checking each element for leftmost middle element while they are equal ; Calculate the number of elements in right of rightmost middle element ; Calculate the number of elements in left of leftmost middle element ; Add selected even length subsets to the answer ; Driver code
mod = 1000000007 NEW_LINE def fact ( n ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT res = res * i NEW_LINE DEDENT return res NEW_LINE DEDENT def nCr ( n , r ) : NEW_LINE INDENT return int ( fact ( n ) / ( fact ( r ) * fact ( n - r ) ) ) NEW_LINE DEDENT def powmod ( a , n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT pt = powmod ( a , int ( n / 2 ) ) NEW_LINE pt = ( pt * pt ) % mod NEW_LINE if ( n % 2 ) : NEW_LINE INDENT return ( pt * a ) % mod NEW_LINE DEDENT else : NEW_LINE INDENT return pt NEW_LINE DEDENT DEDENT def CountSubset ( arr , n ) : NEW_LINE INDENT ans = powmod ( 2 , n - 1 ) NEW_LINE arr . sort ( reverse = False ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT j = i + 1 NEW_LINE while ( j < n and arr [ j ] == arr [ i ] ) : NEW_LINE INDENT r = n - 1 - j NEW_LINE l = i NEW_LINE ans = ( ans + nCr ( l + r , l ) ) % mod NEW_LINE j += 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( CountSubset ( arr , n ) ) NEW_LINE DEDENT