🔥🧭Beats 99.99% |🚩Optimised Code Using Dynamic Programming | 💡🚀🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about finding the number of binary trees that can be formed using a give
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about finding the number of binary trees that can be formed using a given array of integers. Each integer can be used multiple times, and the non-leaf nodes\' values should be the product of the values of their children. This suggests a dynamic programming approach. The code uses a bottom-up dynamic programming approach to count the number of binary trees for each value in the array.\n\n---\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the input array `arr` in ascending order. Sorting helps in ensuring that smaller numbers are processed before larger numbers, which is crucial for the dynamic programming approach.\n\n2. Initialize an unordered map `dp`, where the keys are values from `arr`, and the values are the number of binary trees that can be formed using that value.\n\n3. Iterate through the sorted `arr`. For each value `arr[i]`:\n\n- Initialize `dp[arr[i]]` to 1 because a single node tree with the value `arr[i]` is always possible.\n\n4. Nested within the loop from step 3, iterate over the values in `arr` before the current value (from `0` to `i - 1`). For each value `arr[j]`, check if it\'s a factor of `arr[i]`. If it is, then:\n\n- Calculate the factor as `factor = arr[i] / arr[j]`.\n- If `dp` already contains `factor`, it means that we have already computed the number of binary trees for `factor`.\n- Update `dp[arr[i]]` by adding the product of the number of trees for `arr[j]` and `factor` to it.\n\n5. After the loops, `dp` will contain the number of binary trees that can be formed for each value in `arr`.\n\n6. Sum up all the values in `dp` to get the total number of binary trees.\n\n7. Return the result modulo `10^9 + 7` to avoid integer overflow.\n\n---\n\n# Complexity\n## 1. Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Sorting the array takes O(n * log(n)) time.\n- The nested loop iterates through each element in `arr`, so it\'s O(n^2) in the worst case.\n- The final loop to calculate the result takes O(n).\n- Overall, the time complexity is O(n^2) due to the nested loop.\n## 2. Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- The space complexity is O(n) for the unordered map `dp`.\n\n---\n\n# \uD83D\uDCA1If you have come this far, then i would like to request you to please upvote this solution\u2763\uFE0F\uD83D\uDCA1So that it could reach out to another one\uD83D\uDD25\uD83D\uDD25\n\n---\n\n\n# Code\n\n\n```C++ []\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        int MOD = 1000000007;\n        sort(arr.begin(), arr.end()); // Sort the array.\n\n        unordered_map<int, long long> dp; // Use a map to store the number of trees for each value.\n\n        for (int i = 0; i < arr.size(); i++) {\n            dp[arr[i]] = 1; // A single node tree with the value arr[i].\n            for (int j = 0; j < i; j++) {\n                if (arr[i] % arr[j] == 0) { // If arr[j] is a factor of arr[i].\n                    int factor = arr[i] / arr[j];\n                    if (dp.count(factor)) {\n                        dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[factor]) % MOD;\n                    }\n                }\n            }\n        }\n\n        long long result = 0;\n        for (auto& entry : dp) {\n            result = (result + entry.second) % MOD;\n        }\n\n        return static_cast<int>(result);\n    }\n};\n```\n```Java []\nclass Solution {\n    public int numFactoredBinaryTrees(int[] arr) {\n        int MOD = 1000000007;\n        Arrays.sort(arr);\n        Map<Integer, Long> dp = new HashMap<>();\n        \n        for (int i = 0; i < arr.length; i++) {\n            dp.put(arr[i], 1L);\n            for (int j = 0; j < i; j++) {\n                if (arr[i] % arr[j] == 0) {\n                    int factor = arr[i] / arr[j];\n                    if (dp.containsKey(factor)) {\n                        dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j) * dp.get(factor)) % MOD);\n                    }\n                }\n            }\n        }\n        \n        long result = 0;\n        for (long value : dp.values()) {\n            result = (result + value) % MOD;\n        }\n        \n        return (int) result;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def numFactoredBinaryTrees(self, arr):\n        MOD = 10**9 + 7\n        arr.sort()\n        dp = {}\n        \n        for i in range(len(arr)):\n            dp[arr[i]] = 1\n            for j in range(i):\n                if arr[i] % arr[j] == 0:\n                    factor = arr[i] // arr[j]\n                    if factor in dp:\n                        dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[factor]) % MOD\n        \n        result = 0\n        for value in dp.values():\n            result = (result + value) % MOD\n        \n        return result\n\n```\n```Javascript []\nvar numFactoredBinaryTrees = function(arr) {\n    const MOD = 1000000007;\n    arr.sort((a, b) => a - b);\n    const dp = {};\n    \n    for (let i = 0; i < arr.length; i++) {\n        dp[arr[i]] = 1;\n        for (let j = 0; j < i; j++) {\n            if (arr[i] % arr[j] === 0) {\n                const factor = arr[i] / arr[j];\n                if (dp.hasOwnProperty(factor)) {\n                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[factor]) % MOD;\n                }\n            }\n        }\n    }\n    \n    let result = 0;\n    for (const value of Object.values(dp)) {\n        result = (result + value) % MOD;\n    }\n    \n    return result;\n};\n\n```\n```Ruby []\ndef num_factored_binary_trees(arr)\n    mod = 10**9 + 7\n    arr.sort!\n    dp = {}\n    \n    (0...arr.length).each do |i|\n        dp[arr[i]] = 1\n        (0...i).each do |j|\n            if arr[i] % arr[j] == 0\n                factor = arr[i] / arr[j]\n                if dp.key?(factor)\n                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[factor]) % mod\n                end\n            end\n        end\n    end\n    \n    result = 0\n    dp.values.each do |value|\n        result = (result + value) % mod\n    end\n    \n    result\nend\n\n```\n\n\n\n\n
['Array', 'Hash Table', 'Dynamic Programming', 'Sorting', 'C++', 'Java', 'Python3', 'Ruby', 'JavaScript']