Count number of subsets whose median is also present in the same subset | Python3 implementation of the approach ; Function to store pascal triangle in 2 - d array ; 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 arr = [ [ None for i in range ( 1001 ) ] for j in range ( 1001 ) ] NEW_LINE def Preprocess ( ) : NEW_LINE INDENT arr [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , 1001 ) : NEW_LINE INDENT arr [ i ] [ 0 ] = 1 NEW_LINE for j in range ( 1 , i ) : NEW_LINE INDENT arr [ i ] [ j ] = ( arr [ i - 1 ] [ j - 1 ] + arr [ i - 1 ] [ j ] ) % mod NEW_LINE DEDENT arr [ i ] [ i ] = 1 NEW_LINE DEDENT DEDENT def powmod ( a , n ) : NEW_LINE INDENT if not n : NEW_LINE INDENT return 1 NEW_LINE DEDENT pt = powmod ( a , 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 ( val , n ) : NEW_LINE INDENT ans = powmod ( 2 , n - 1 ) NEW_LINE val . sort ( ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT j = i + 1 NEW_LINE while j < n and val [ j ] == val [ i ] : NEW_LINE INDENT r = n - 1 - j NEW_LINE l = i NEW_LINE ans = ( ans + arr [ l + r ] [ l ] ) % mod NEW_LINE j += 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT Preprocess ( ) NEW_LINE val = [ 2 , 3 , 2 ] NEW_LINE n = len ( val ) NEW_LINE print ( CountSubset ( val , n ) ) NEW_LINE DEDENT