aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rwxr-xr-x823/main.py37
1 files changed, 37 insertions, 0 deletions
diff --git a/823/main.py b/823/main.py
new file mode 100755
index 0000000..debdec0
--- /dev/null
+++ b/823/main.py
@@ -0,0 +1,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()