C++ DP Solution O(N ^ 2)
Runtime: 77 ms, faster than 71.87% of C++ online submissions for Binary Trees With Factors.\nMemory Usage: 9.2 MB, less than 77.68% of C++ online submissions fo
Runtime: 77 ms, faster than 71.87% of C++ online submissions for Binary Trees With Factors.\nMemory Usage: 9.2 MB, less than 77.68% of C++ online submissions for Binary Trees With Factors.\n\n\n```\nWe can get the tree count for current number from the tree count of the factors of the current number.\nSo, Binary Tree count for num => DP[num] += DP[X] * DP[num/X] where X and num/X are factors\n\n1. Sort the numbers and process smaller numbers first as they will be the factor of larger number\n2. Then loop from first to current number and check if previous values are factors of current number \nupdate tree count for number using DP equation\n3. User Hash Table to track the count of tree for each number as root\n```\n\n\n```\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        \n        int n = arr.size();\n        sort(arr.begin(),arr.end());\n\n        // track the tree count for each number as root\n        unordered_map<int,long long>dp;\n        long long count = 0;\n        int MOD = 1000000007;\n        \n        for(int i=0;i<n;i++)\n        {\n            dp[arr[i]] = 1L;    // each number is root itself\n            \n            for(int j=0;j<i;j++)\n            {\n                if((arr[i] % arr[j]) == 0)\n                {\n                    // both factor present in dp, then add the tree count\n                    if(dp.find(arr[i]/arr[j])!=dp.end())\n                        dp[arr[i]] =  (dp[arr[i]] + dp[arr[j]] * dp[arr[i]/arr[j]]) % MOD;\n                }                \n            }\n            \n            count = (count + dp[arr[i]]) % MOD;\n        }\n        \n        return count;   // total tree count\n    }\n};\n```
['Dynamic Programming', 'C', 'Sorting']