Number of full binary trees such that each node is product of its children | Return the number of all possible full binary tree with given product property . ; Finding the minimum and maximum values in given array . ; Marking the presence of each array element and initialising the number of possible full binary tree for each integer equal to 1 because single node will also contribute as a full binary tree . ; From minimum value to maximum value of array finding the number of all possible Full Binary Trees . ; Find if value present in the array ; For each multiple of i , less than equal to maximum value of array ; If multiple is not present in the array then continue . ; Finding the number of possible Full binary trees for multiple j by multiplying number of possible Full binary tree from the number i and number of possible Full binary tree from i / j . ; Condition for possiblity when left chid became right child and vice versa . ; Driver Code
def numoffbt ( arr , n ) : NEW_LINE INDENT maxvalue = - 2147483647 NEW_LINE minvalue = 2147483647 NEW_LINE for i in range ( n ) : NEW_LINE INDENT maxvalue = max ( maxvalue , arr [ i ] ) NEW_LINE minvalue = min ( minvalue , arr [ i ] ) NEW_LINE DEDENT mark = [ 0 for i in range ( maxvalue + 2 ) ] NEW_LINE value = [ 0 for i in range ( maxvalue + 2 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT mark [ arr [ i ] ] = 1 NEW_LINE value [ arr [ i ] ] = 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( minvalue , maxvalue + 1 ) : NEW_LINE INDENT if ( mark [ i ] != 0 ) : NEW_LINE INDENT j = i + i NEW_LINE while ( j <= maxvalue and j // i <= i ) : NEW_LINE INDENT if ( mark [ j ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT value [ j ] = value [ j ] + ( value [ i ] * value [ j // i ] ) NEW_LINE if ( i != j // i ) : NEW_LINE INDENT value [ j ] = value [ j ] + ( value [ i ] * value [ j // i ] ) NEW_LINE DEDENT j += i NEW_LINE DEDENT DEDENT ans += value [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 2 , 3 , 4 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( numoffbt ( arr , n ) ) NEW_LINE