Number of ways to form a heap with n distinct integers | 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
let dp = new Array ( MAXN ) ; let nck = new Array ( MAXN ) ; for ( let i = 0 ; i < MAXN ; i ++ ) { nck [ i ] = new Array ( MAXN ) ; for ( let j = 0 ; j < MAXN ; j ++ ) nck [ i ] [ j ] = 0 ; } let log2 = new Array ( MAXN ) ; function choose ( n , 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 ] ; } let answer = choose ( n - 1 , k - 1 ) + choose ( n - 1 , k ) ; nck [ n ] [ k ] = answer ; return answer ; } function getLeft ( n ) { if ( n == 1 ) { return 0 ; } let h = log2 [ n ] ; let last = n - ( ( 1 << h ) - 1 ) ; if ( last >= ( numh / 2 ) ) { } else { return ( 1 << h ) - 1 - ( ( numh / 2 ) - last ) ; } } function numberOfHeaps ( n ) { if ( n <= 1 ) { return 1 ; } if ( dp [ n ] != - 1 ) { return dp [ n ] ; } let left = getLeft ( n ) ; let ans = ( choose ( n - 1 , left ) * numberOfHeaps ( left ) ) * ( numberOfHeaps ( n - 1 - left ) ) ; dp [ n ] = ans ; return ans ; } function solve ( n ) { for ( let i = 0 ; i <= n ; i ++ ) { dp [ i ] = - 1 ; } for ( let i = 0 ; i <= n ; i ++ ) { for ( let j = 0 ; j <= n ; j ++ ) { nck [ i ] [ j ] = - 1 ; } } let currLog2 = - 1 ; let currPower2 = 1 ; for ( let i = 1 ; i <= n ; i ++ ) { if ( currPower2 == i ) { currLog2 ++ ; currPower2 *= 2 ; } log2 [ i ] = currLog2 ; } return numberOfHeaps ( n ) ; } let n = 10 ; document . write ( solve ( n ) ) ;