Count number of subsets whose median is also present in the same subset | C ++ 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
#include <algorithm> NEW_LINE #include <iostream> NEW_LINE using namespace std ; long long mod = 1000000007 ; int fact ( int n ) { int res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) res = res * i ; return res ; } int nCr ( int n , int r ) { return fact ( n ) / ( fact ( r ) * fact ( n - r ) ) ; } long long powmod ( long long a , long long n ) { if ( ! n ) return 1 ; long long pt = powmod ( a , n / 2 ) ; pt = ( pt * pt ) % mod ; if ( n % 2 ) return ( pt * a ) % mod ; else return pt ; } long long CountSubset ( int * arr , int n ) { long long ans = powmod ( 2 , n - 1 ) ; sort ( arr , arr + n ) ; for ( int i = 0 ; i < n ; ++ i ) { int j = i + 1 ; while ( j < n && arr [ j ] == arr [ i ] ) { int r = n - 1 - j ; int l = i ; ans = ( ans + nCr ( l + r , l ) ) % mod ; j ++ ; } } return ans ; } int main ( ) { int arr [ ] = { 2 , 3 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << CountSubset ( arr , n ) << endl ; return 0 ; }