✅✅Faster || Easy To Understand || C++ Code
Using Dp && Hashmap\n\n Time Complexity :- O(N * N)\n\n Space Complexity :- O(N)\n\n\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr
* ***Using Dp && Hashmap***\n\n* ***Time Complexity :- O(N * N)***\n\n* ***Space Complexity :- O(N)***\n\n```\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        \n        int n = arr.size();\n        \n        long long mod = 1e9 + 7;\n        \n        // first of all sort the array\n        \n        sort(arr.begin(), arr.end());\n        \n        // declare a dp, dp[i] will store the possible binary tree till ith index\n        \n        vector<int> dp(n, 1);\n        \n        // declare a map, {value -> index}\n        \n        unordered_map<int, int> mp;\n        \n        // store the index to corresponding element\n        \n        for(int i = 0; i < n; i++)\n        {\n            mp[arr[i]] = i;\n        }\n        \n        // fill the dp\n        \n        for(int i = 0; i < n; i++)\n        {\n            for(int j = 0; j < i; j++)\n            {\n                // if we found one factor\n                \n                if(arr[i] % arr[j] == 0)\n                {\n                    // check if other corresponding factor is present in arr or not\n                    \n                    if(mp.count(arr[i] / arr[j]))\n                    {\n                        // find the index of other factor\n                        \n                        int idx = mp[arr[i] / arr[j]];\n                        \n                        // update the dp[i] \n                        \n                        dp[i] = (dp[i] % mod + (dp[j] % mod * dp[idx] % mod)) % mod;\n                    }\n                }\n            }\n        }\n        \n        // at the end just sum up all the values of dp\n        \n        int total = 0;\n        \n        for(int i = 0; i < n; i++)\n        {\n            total = (total % mod + dp[i] % mod) % mod;\n        }\n        \n        return total;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']