Number of ways to form a heap with n distinct integers | Java program to count max heaps with n distinct keys ; dp [ i ] = number of max heaps for i distinct integers ; nck [ i ] [ j ] = number of ways to choose j elements form i elements , no order ; log2 [ i ] = floor of logarithm of base 2 of i ; to calculate nCk ; calculate l for give value of n ; number of elements that are actually present in last level ( hth level ) ( 2 ^ h - 1 ) ; if more than half - filled ; return ( 1 << h ) - 1 ; ( 2 ^ h ) - 1 ; find maximum number of heaps for n ; function to initialize arrays ; for each power of two find logarithm ; Driver code
class GFG { static int [ ] dp = new int [ MAXN ] ; static int [ ] [ ] nck = new int [ MAXN ] [ MAXN ] ; static int [ ] log2 = new int [ MAXN ] ; public static int choose ( int n , int k ) { if ( k > n ) { return 0 ; } if ( n <= 1 ) { return 1 ; } if ( k == 0 ) { return 1 ; } if ( nck [ n ] [ k ] != - 1 ) { return nck [ n ] [ k ] ; } int answer = choose ( n - 1 , k - 1 ) + choose ( n - 1 , k ) ; nck [ n ] [ k ] = answer ; return answer ; } public static int getLeft ( int n ) { if ( n == 1 ) { return 0 ; } int h = log2 [ n ] ; int last = n - ( ( 1 << h ) - 1 ) ; if ( last >= ( numh / 2 ) ) { } else { return ( 1 << h ) - 1 - ( ( numh / 2 ) - last ) ; } } public static int numberOfHeaps ( int n ) { if ( n <= 1 ) { return 1 ; } if ( dp [ n ] != - 1 ) { return dp [ n ] ; } int left = getLeft ( n ) ; int ans = ( choose ( n - 1 , left ) * numberOfHeaps ( left ) ) * ( numberOfHeaps ( n - 1 - left ) ) ; dp [ n ] = ans ; return ans ; } public static int solve ( int n ) { for ( int i = 0 ; i <= n ; i ++ ) { dp [ i ] = - 1 ; } for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { nck [ i ] [ j ] = - 1 ; } } int currLog2 = - 1 ; int currPower2 = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( currPower2 == i ) { currLog2 ++ ; currPower2 *= 2 ; } log2 [ i ] = currLog2 ; } return numberOfHeaps ( n ) ; } public static void main ( String [ ] args ) { int n = 10 ; System . out . print ( solve ( n ) ) ; } }