aboutsummaryrefslogtreecommitdiffstats
path: root/823/main.py
blob: debdec09ffc30cd726d4c7247ba9ba805ca2e203 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/usr/bin/env python3
# not mine

from typing import List


class Solution:
    def __init__(self):
        self.memo = {}
        self.num_list = {}

    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        modulo: int = 10**9 + 7
        N: int = len(arr)
        arr.sort()
        dp = [1] * N
        index = {x: i for i, x in enumerate(arr)}

        for i, x in enumerate(arr):
            for j in range(i):
                if x % arr[j] == 0:
                    right = x / arr[j]
                    if right in index:
                        dp[i] += dp[j] * dp[int(index[int(right)])]
                        dp[i] %= modulo

        return sum(dp) % modulo


def main():
    solution = Solution()
    assert solution.numFactoredBinaryTrees([2, 4]), 3
    assert solution.numFactoredBinaryTrees([2, 4, 5, 10]), 7


if __name__ == "__main__":
    main()