✅ Beats 100% 🔥 || Easiest Approach in 3 Points || DP & HashMap
TypeScript Result:\n\n\n\n# Intuition :\nIn order to build a tree, we need to know the number of left children and right children. \nIf we know the number of le
##### TypeScript Result:\n![image.png](https://assets.leetcode.com/users/images/9ff22734-7791-410d-a9c8-db3b124aebda_1698290459.4343364.png)\n\n\n# Intuition :\n**In order to build a tree, we need to know the number of left children and right children. \nIf we know the number of left children and right children, the total number of trees we can build is left * right.\nSo we can use a hashmap to store the number of trees we can build for each number.\nWe iterate the array from small to big, for each number, we iterate all the numbers smaller than it to find the left children,\nand we check if the right children exists in the hashmap.\nIf so, we can build left * right trees.\nFinally, we sum up the number of trees for each number.**\n\n# Algorithm :\n1. Sort the array "arr", and use a hashmap dp to record the number of trees we can build for each number.\n2. Iterate the array from small to big, for each number, we iterate all the numbers smaller than it to find the left children, and we check if the right children exists in the hashmap. If so, we can build left * right trees.\n3. Finally, we sum up the number of trees for each number.\n\n# Complexity Analysis :\n- $$Time Complexity$$: **O(N^2)**, where N is the length of arr. For each arr[i], we iterate arr[j] to find the left children, and check if arr[i] / arr[j] exists in the hashmap.\n- $$Space Complexity$$: **O(N)**, the space used by hashmap dp.\n\n### UpVote \u2B06\uFE0F if you found this helpful :)\n\n# Code\n``` Python []\nclass Solution:\n    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n        arr.sort()\n        dp = {}\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 and arr[i] // arr[j] in dp:\n                    dp[arr[i]] += dp[arr[j]] * dp[arr[i] // arr[j]]\n        return sum(dp.values()) % (10**9 + 7)\n```\n``` C++ []\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        std::sort(arr.begin(), arr.end());\n        std::unordered_map<int, long> dp;\n\n        for (int i = 0; i < arr.size(); i++) {\n            dp[arr[i]] = 1;\n\n            for (int j = 0; j < i; j++) {\n                if (arr[i] % arr[j] == 0 && dp.find(arr[i] / arr[j]) != dp.end()) {\n                    dp[arr[i]] += dp[arr[j]] * dp[arr[i] / arr[j]];\n                }\n            }\n        }\n\n        long result = 0;\n        for (auto val : dp) {\n            result += val.second;\n        }\n\n        return result % (int)(1e9 + 7);\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int numFactoredBinaryTrees(int[] arr) {\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\n            for (int j = 0; j < i; j++) {\n                if (arr[i] % arr[j] == 0 && dp.containsKey(arr[i] / arr[j])) {\n                    dp.put(arr[i], dp.get(arr[i]) + dp.get(arr[j]) * dp.get(arr[i] / arr[j]));\n                }\n            }\n        }\n\n        long result = 0;\n        for (long val : dp.values()) {\n            result += val;\n        }\n\n        return (int) (result % (Math.pow(10, 9) + 7));\n    }\n}\n```\n``` C# []\npublic class Solution {\n    public int NumFactoredBinaryTrees(int[] arr) {\n        Array.Sort(arr);\n        Dictionary<int, long> dp = new Dictionary<int, long>();\n\n        foreach (int i in arr) {\n            dp[i] = 1;\n\n            foreach (int j in arr) {\n                if (i % j == 0 && dp.ContainsKey(i / j)) {\n                    dp[i] += dp[j] * dp[i / j];\n                }\n            }\n        }\n\n        long result = 0;\n        foreach (var val in dp.Values) {\n            result += val;\n        }\n\n        return (int)(result % (Math.Pow(10, 9) + 7));\n    }\n}\n```\n``` JavaScipt []\nvar numFactoredBinaryTrees = function(arr) {\n    arr.sort((a, b) => a - b);\n        const dp = new Map();\n\n        for (let i = 0; i < arr.length; i++) {\n            dp.set(arr[i], 1);\n\n            for (let j = 0; j < i; j++) {\n                if (arr[i] % arr[j] === 0 && dp.has(arr[i] / arr[j])) {\n                    dp.set(arr[i], dp.get(arr[i]) + dp.get(arr[j]) * dp.get(arr[i] / arr[j]));\n                }\n            }\n        }\n\n        let result = 0;\n        for (const val of dp.values()) {\n            result += val;\n        }\n\n        return result % (Math.pow(10, 9) + 7);\n};\n\n```\n``` TypeScipt []\nfunction numFactoredBinaryTrees(arr: number[]): number {\narr.sort((a, b) => a - b);\n        const dp: Map<number, number> = new Map();\n\n        for (let i = 0; i < arr.length; i++) {\n            dp.set(arr[i], 1);\n\n            for (let j = 0; j < i; j++) {\n                if (arr[i] % arr[j] === 0 && dp.has(arr[i] / arr[j])) {\n                    dp.set(arr[i], dp.get(arr[i])! + dp.get(arr[j])! * dp.get(arr[i] / arr[j])!);\n                }\n            }\n        }\n\n        let result = 0;\n        for (const val of dp.values()) {\n            result += val;\n        }\n\n        return result % (Math.pow(10, 9) + 7);\n};\n```\n``` PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $arr\n     * @return Integer\n     */\n    function numFactoredBinaryTrees($arr) {\n        sort($arr);\n        $dp = array();\n\n        foreach ($arr as $i) {\n            $dp[$i] = 1;\n\n            foreach ($arr as $j) {\n                if ($i % $j === 0 && isset($dp[$i / $j])) {\n                    $dp[$i] += $dp[$j] * $dp[$i / $j];\n                }\n            }\n        }\n\n        $result = 0;\n        foreach ($dp as $val) {\n            $result += $val;\n        }\n\n        return $result % (pow(10, 9) + 7);\n    }\n}\n```\n``` Ruby []\n# @param {Integer[]} arr\n# @return {Integer}\ndef num_factored_binary_trees(arr)\n    arr.sort!\n        dp = {}\n\n        arr.each do |i|\n            dp[i] = 1\n\n            arr.each do |j|\n                if i % j == 0 && dp.key?(i / j)\n                    dp[i] += dp[j] * dp[i / j]\n                end\n            end\n        end\n\n        result = 0\n        dp.values.each { |val| result += val }\n\n        result % (10**9 + 7)\n    end\n```\n\n![image.png](https://assets.leetcode.com/users/images/3a7da442-f8cf-4201-9e84-a2cc0ad563f0_1698290282.6644006.png)\n
['Hash Table', 'Dynamic Programming', 'PHP', 'C++', 'Java', 'TypeScript', 'Python3', 'Ruby', 'JavaScript', 'C#']