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
dp = [ 0 ] * MAXN NEW_LINE nck = [ [ 0 for i in range ( MAXN ) ] for j in range ( MAXN ) ] NEW_LINE log2 = [ 0 ] * MAXN NEW_LINE def choose ( n , k ) : NEW_LINE INDENT if ( k > n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n <= 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( k == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( nck [ n ] [ k ] != - 1 ) : NEW_LINE INDENT return nck [ n ] [ k ] NEW_LINE DEDENT answer = choose ( n - 1 , k - 1 ) + choose ( n - 1 , k ) NEW_LINE nck [ n ] [ k ] = answer NEW_LINE return answer NEW_LINE DEDENT def getLeft ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT h = log2 [ n ] NEW_LINE last = n - ( ( 1 << h ) - 1 ) NEW_LINE if ( last >= ( numh // 2 ) ) : NEW_LINE else : NEW_LINE INDENT return ( 1 << h ) - 1 - ( ( numh // 2 ) - last ) NEW_LINE DEDENT DEDENT def numberOfHeaps ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ n ] != - 1 ) : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT left = getLeft ( n ) NEW_LINE ans = ( choose ( n - 1 , left ) * numberOfHeaps ( left ) ) * ( numberOfHeaps ( n - 1 - left ) ) NEW_LINE dp [ n ] = ans NEW_LINE return ans NEW_LINE DEDENT def solve ( n ) : NEW_LINE INDENT for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] = - 1 NEW_LINE DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT nck [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT currLog2 = - 1 NEW_LINE currPower2 = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( currPower2 == i ) : NEW_LINE INDENT currLog2 += 1 NEW_LINE currPower2 *= 2 NEW_LINE DEDENT log2 [ i ] = currLog2 NEW_LINE DEDENT return numberOfHeaps ( n ) NEW_LINE DEDENT n = 10 NEW_LINE print ( solve ( n ) ) NEW_LINE