Number of ways to form a heap with n distinct integers | CPP 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 function
#include <iostream> NEW_LINE using namespace std ; int dp [ MAXN ] ; int nck [ MAXN ] [ MAXN ] ; int log2 [ MAXN ] ; 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 ; } 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 ) ; } 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 ; } 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 ) ; } int main ( ) { int n = 10 ; cout << solve ( n ) << endl ; return 0 ; }