aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_factors.py
diff options
context:
space:
mode:
Diffstat (limited to 'binary_tree_factors.py')
-rw-r--r--binary_tree_factors.py24
1 files changed, 24 insertions, 0 deletions
diff --git a/binary_tree_factors.py b/binary_tree_factors.py
new file mode 100644
index 0000000..03fc3f5
--- /dev/null
+++ b/binary_tree_factors.py
@@ -0,0 +1,24 @@
+# 823. Binary Trees With Factors
+
+"""
+given an array of unique integers 'arr' where each integer 'arr[i]' is
+strictly greater than 1. we make a binary tree using these integers and each
+number may be used for any number of times. each non-leaf node's value should
+be equal to the product of the values of its children. return the number of
+binary trees we can make. the answer may be too large to fit in a signed 32
+bit integer, so return the answer modulo 10e9+7
+"""
+
+
+class Solution(object):
+ def numFactoredBinaryTrees(self, arr):
+ dp = {}
+ for i in sorted(arr):
+ dp[i] = sum(dp[b] * dp.get(i / b, 0) for b in dp if i % b == 0) + 1
+ return sum(dp.values()) % (10**9 + 7)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numFactoredBinaryTrees([2, 4])) # expect: 3
+ print(obj.numFactoredBinaryTrees([2, 4, 5, 10])) # expect: 7