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()
|
