Count number of subsets whose median is also present in the same subset | PHP 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
< ? php $ mod = 1000000007 ; function fact ( $ n ) { $ res = 1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) $ res = $ res * $ i ; return $ res ; } function nCr ( $ n , $ r ) { return fact ( $ n ) / ( fact ( $ r ) * fact ( $ n - $ r ) ) ; } function powmod ( $ a , $ n ) { global $ mod ; if ( $ n == 0 ) return 1 ; $ pt = powmod ( $ a , $ n / 2 ) ; $ pt = ( $ pt * $ pt ) % $ mod ; if ( $ n % 2 == 1 ) return ( $ pt * $ a ) % $ mod ; else return $ pt ; } function CountSubset ( $ arr , $ n ) { global $ mod ; $ ans = powmod ( 2 , $ n - 1 ) ; sort ( $ arr , 0 ) ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) { $ j = $ i + 1 ; while ( $ j < $ n && $ arr [ $ j ] == $ arr [ $ i ] ) { $ r = $ n - 1 - $ j ; $ l = $ i ; $ ans = ( $ ans + nCr ( $ l + $ r , $ l ) ) % $ mod ; $ j ++ ; } } return $ ans ; } { $ arr = array ( 2 , 3 , 2 ) ; $ n = sizeof ( $ arr ) ; echo ( CountSubset ( $ arr , $ n ) ) ; }