Number of full binary trees such that each node is product of its children | C ++ program to find number of full binary tree 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 . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int numoffbt ( int arr [ ] , int n ) { int maxvalue = INT_MIN , minvalue = INT_MAX ; for ( int i = 0 ; i < n ; i ++ ) { maxvalue = max ( maxvalue , arr [ i ] ) ; minvalue = min ( minvalue , arr [ i ] ) ; } int mark [ maxvalue + 2 ] ; int value [ maxvalue + 2 ] ; memset ( mark , 0 , sizeof ( mark ) ) ; memset ( value , 0 , sizeof ( value ) ) ; for ( int i = 0 ; i < n ; i ++ ) { mark [ arr [ i ] ] = 1 ; value [ arr [ i ] ] = 1 ; } int ans = 0 ; for ( int i = minvalue ; i <= maxvalue ; i ++ ) { if ( mark [ i ] ) { for ( int j = i + i ; j <= maxvalue && j / i <= i ; j += i ) { if ( ! mark [ j ] ) continue ; value [ j ] = value [ j ] + ( value [ i ] * value [ j / i ] ) ; if ( i != j / i ) value [ j ] = value [ j ] + ( value [ i ] * value [ j / i ] ) ; } } ans += value [ i ] ; } return ans ; } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << numoffbt ( arr , n ) << endl ; return 0 ; }