Binary Tree With Factors, C++ Explained Solution
The question here is quite good and needs some good observations. Lets try to find how will we count this number of trees. Lets take an array : [2 , 4 , 5 , 10 
The question here is quite good and needs some good observations. Lets try to find how will we count this number of trees. Lets take an array : **[2 , 4 , 5 , 10 , 20]**. Now we know that **2** and **5** will form only a single tree because they are prime. What about **4, 10 and 20 ?**. Lets see, basically every number can be a binary tree of single node with this number as the root but for composite numbers they can also be subdivided into its factors. Now lets take **4**, Now since 4 has only **2** as its other factor **( 1 is not considered cause it has been considered already when number itself is root, moreover array will contain numbers only greater than 1 )** . Since **2** and **4/2 = 2** are same only thus swapping them as right and left child will not create a new tree. Thus we need to count this only once. But lets take **10**, Now 10 can be single (root only) and **10** can be divided into **2** and **5** too. Since both of them are different and both of them are present in the array also thus for this pair we have **2 distinct trees**. Thus recursive relation looks something like :\n\n**ans = ans + ways(i) x ways(num/i)**\n\n**Note num should be divisible by i.  Secondly the value of ans = 1 initially, this is done to count the trees when tree consists of only a single node (number itself). We could also have used a loop for factorising num but by this way we would encounter a lot of numbers that are useless cause they might not be present inside the array. So its better that we focus on the numbers that are given in the array. By this way we also reduce the time complexity. Also we use a hashmap for storing DP states cause numbers are very big**. 2 Code implementations are given below :\n\n**Implementation 1 : Less Optimised**\nTime Complexity :  O(N x Sum(root(A[i]))) for all i from **0 to N-1**\nSpace Complexity : O(N), cause we store results only for numbers in the array.\n**PS : You can also see that there is also a bit change in recursive relation in this implementation**\n\nCode :\n```\nclass Solution {\n    #define ll long long\npublic:\n    map<ll,ll>mp;\n    map<ll,ll>dp;\n    ll mod = 1e9+7;\n    ll ways(ll val){\n        if(dp.find(val)!=dp.end()){\n            return dp[val];\n        }\n        ll ans = 1;\n        for(ll j = 2; j*j<=val; j++){\n            if(val%j==0){\n                if(mp.find(j)!=mp.end() && mp.find(val/j)!=mp.end()){\n                    if(j*j==val){\n                        ll prod = ways(j)*ways(val/j);\n                        prod%=mod;\n                        ans+=prod;\n                        ans%=mod;\n                    }\n                    else{\n                        ll prod = ways(j)*ways(val/j);\n                        prod%=mod;\n                        prod = (prod*2)%mod;\n                        ans+=prod;\n                        ans%=mod;\n                    }\n                }\n            }\n        }\n        return dp[val] = ans;\n    }\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        ios_base::sync_with_stdio(0);\n        int n = arr.size();\n        for(auto it : arr){\n            mp[it]++;\n        }\n        ll ans = 0;\n        for(int i = 0; i<n; i++){            \n\t\t\tans+=ways(arr[i]);\n            ans%=mod;\n        }\n        dp.clear();\n        mp.clear();\n        return ans;\n    }\n};\n```\n\n\n\n**Implementation 2 : Most Optimised**\nTime Complexity : O(N^2)\nSpace Complexity : O(N), cause we are storing results for numbers that are present in array else not.\n\nCode : \n```\nclass Solution {\n    #define ll long long\npublic:\n    map<ll,ll>mp;\n    map<ll,ll>dp;\n    ll mod = 1e9+7;\n    ll ways(ll val){\n        if(dp.find(val)!=dp.end()){\n            return dp[val];\n        }\n        ll ans = 1;\n        for(auto it : mp){\n            ll j = it.first;\n            if(val%j==0 && mp.find(val/j)!=mp.end()){\n                ll prod = ways(j)*ways(val/j);\n                prod%=mod;\n                ans+=prod;\n                ans%=mod;\n            }\n        }\n        return dp[val] = ans;\n    }\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        ios_base::sync_with_stdio(0);\n        int n = arr.size();\n        for(auto it : arr){\n            mp[it]++;\n        }\n        ll ans = 0;\n        for(int i = 0; i<n; i++){\n            ans+=ways(arr[i]);\n            ans%=mod;\n        }\n        dp.clear();\n        mp.clear();\n        return ans;\n    }\n};\n```\n**Do Upvote If Found Helpful !**
['Math', 'Dynamic Programming', 'Recursion', 'C', 'C++']