From 6a5f0f381928ca5b54b1e01a6e46baeaa91cbaca Mon Sep 17 00:00:00 2001 From: terminaldweller Date: Tue, 9 Aug 2022 11:18:28 +0430 Subject: update --- 823/main.py | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100755 823/main.py (limited to '823') 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() -- cgit v1.2.3