🔥DP on Trees || 💯HashTable || ✅⚡Clean Code
\n\n# Complexity\n\n- Time complexity:\nO(n * n)\n\n- Space complexity:\nO(n)\n\n\n# Code\n\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    int nu
\n\n# Complexity\n```\n- Time complexity:\nO(n * n)\n\n- Space complexity:\nO(n)\n```\n\n# Code\n```\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        int n = arr.size(), ans = 0;\n        unordered_map<int, long> mp;\n        for(auto it : arr)\n            mp[it]++;\n        sort(arr.begin(), arr.end());\n        int other_child = 0;\n        for(int i = 1 ; i < n ; i++){\n            int root = arr[i];\n            for(int j = 0 ; j < i ; j++){\n                if(arr[i] % arr[j] == 0){\n                    other_child = arr[i] / arr[j];\n                    if(mp.contains(other_child))\n                        mp[root] += mp[arr[j]] * mp[other_child];\n                }\n            }\n        }\n        for(auto it : mp)\n            ans = (ans + it.second) % mod;\n        return ans;\n    }\n};\n```
['Array', 'Hash Table', 'Dynamic Programming', 'Sorting', 'C++']