Count number of subsets whose median is also present in the same subset | Js 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
let mod = 1000000007 ; let arr = [ ] ; for ( let i = 0 ; i < 1001 ; i ++ ) { arr [ i ] = [ ] ; for ( let j = 0 ; j < 1001 ; j ++ ) { arr [ i ] [ j ] = 0 ; } } function Preprocess ( ) { arr [ 0 ] [ 0 ] = 1 ; for ( let i = 1 ; i <= 1000 ; ++ i ) { arr [ i ] [ 0 ] = 1 ; for ( let j = 1 ; j < i ; ++ j ) { arr [ i ] [ j ] = ( arr [ i - 1 ] [ j - 1 ] + arr [ i - 1 ] [ j ] ) % mod ; } arr [ i ] [ i ] = 1 ; } } function powmod ( a , n ) { if ( ! n ) return 1 ; let pt = powmod ( a , Math . floor ( n / 2 ) ) ; pt = ( pt * pt ) % mod ; if ( n % 2 ) return ( pt * a ) % mod ; else return pt ; } function CountSubset ( val , n ) { let ans = powmod ( 2 , n - 1 ) ; val . sort ( function ( a , b ) { return a - b } ) ; for ( let i = 0 ; i < n ; ++ i ) { let j = i + 1 ; while ( j < n && val [ j ] == val [ i ] ) { let r = n - 1 - j ; let l = i ; ans = ( ans + arr [ l + r ] [ l ] ) % mod ; j ++ ; } } return ans ; } Preprocess ( ) ; let val = [ 2 , 3 , 2 ] ; let n = val . length ; document . write ( CountSubset ( val , n ) , ' ' ) ;