🔥 Python || Detailed Explanation ✅ || Easily Understood || DP || O(n * sqrt(n))
Appreciate if you could upvote this solution\n\nMethod: DP\n\nSince the parent node is the product of the children, the value of the parent nodes must larger th
**Appreciate if you could upvote this solution**\n\nMethod: `DP`\n\nSince the parent node is the product of the children, the value of the parent nodes must larger than the values of its children.\nThus, we can sort the `arr` first, and start to calculate the combination of products **from smallest node to the largest one**.\nFor example, `arr = [18, 3, 6, 2]`\nAfter sorting, `arr = [2, 3, 6, 18]`\nThen, a dict `count_product_dict` needs to be created to store the count of combinations and all the initial values should be `1`.\n\n```\nFor 2:\n\t- We can ignore the first number as the smallest number does not have a product of 2 smaller numbers.\n\nFor 3:\n\t- We can just scan the numbers smaller than 3\n\t\t- Since 2 is larger than half of 3, it is rejected as 3 must not be a product of 2 and a integer.\n\nFor 6:\n\t- We can just scan the numbers smaller than 6\n\t\t- 6 % 2 == 0 -> (2, 6 // 2)\n\t\t\t- count_product_dict[6] += count_product_dict[2] * count_product_dict[6 // 2]\n\t\t- 6 % 3 == 0 -> (3, 6 // 3)\n\t\t\t- count_product_dict[6] += count_product_dict[2] * count_product_dict[6 // 2]\n\nAnd so on...\nFinally, count_product_dict = {18: 7, 3: 1, 6: 3, 2: 1}\n```\n\nCode:\n```\nclass Solution:\n    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n        total_nums = len(arr)\n        moduler = 1000000007\n        count_product_dict = {num: 1 for num in arr}\n        arr.sort()\n\n        for i in range(1, total_nums):\n            for j in range(i):\n                quotient = arr[i] // arr[j]\n                if quotient < 2 or math.sqrt(arr[i]) > arr[i- 1]:\n                    break\n                if arr[i] % arr[j] == 0:\n                    count_product_dict[arr[i]] += count_product_dict[arr[j]] * count_product_dict.get(quotient, 0)\n                    count_product_dict[arr[i]] %= moduler\n                    \n        return sum(count_product_dict.values()) % moduler\n```\n\n**Time Complexity**: O(n ^ 2)\n**Space Complexity**: O(n)\n<br />
['Dynamic Programming', 'Python', 'Python3']