[Python3] two approaches
Approach 1 - priority queue \nThe essential argument is that if we find x*y = z in A, then cnt[z] += cnt[x]*cnt[y]. One caveat is that we have to process from s
Approach 1 - priority queue \nThe essential argument is that if we find `x*y = z` in `A`, then `cnt[z] += cnt[x]*cnt[y]`. One caveat is that we have to process from small value to large value to make sure that when updating `z` the count of `x` and `y` are already accurate. \n\nOne straightforward approach is to use a priority queue to store `(z, x, y)` triplet, and process them one by one. \n\nImplementation \n```\nclass Solution:\n    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n        As = set(A) # set for O(1) lookup \n        pq = [] # min heap \n        for x, y in product(A, A): \n            if x*y in As: heappush(pq, (x*y, x, y))\n        \n        cnt = {x: 1 for x in A}\n        while pq: \n            z, x, y = heappop(pq)\n            cnt[z] += cnt[x] * cnt[y]\n        \n        return sum(cnt.values()) % 1_000_000_007\n```\n\nAnalysis\nTime complexity `O(N^2)` on the assumption that `pq` is `O(N)`\nSpace complexity `O(N)` \n\nApproach 2 - greedy \nWe can solve this problem more directly via greedy approach. Scan through `A` from smallest to largest and collect its count. \n\nImplementation \n```\nclass Solution:\n    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n        cnt = {}\n        for x in sorted(A): \n            cnt[x] = 1 + sum(cnt[xx]*cnt[x//xx] for xx in cnt if not x%xx and x//xx in cnt)\n        return sum(cnt.values()) % 1_000_000_007\n```\n\nAnalysis\nTime complexity `O(N^2)`\nSpace complexity `O(N)`\n\nEdited on 3/13/2021\nAdding an easier to follow implementation\n```\nclass Solution:\n    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n        freq = {}\n        for x in sorted(arr): \n            freq[x] = 1\n            for xx in freq: \n                freq[x] += freq[xx] * freq.get(x/xx, 0)\n        return sum(freq.values()) % 1_000_000_007\n```
['Python3']