Leetcode 843 Solution

This article provides solution to leetcode question 843 (binary-trees-with-factors)
Categories:
Tags:
Access this page by simply typing in "lcs 843" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/binary-trees-with-factors

Solution

class Solution(object):
    def numFactoredBinaryTrees(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        m = 10**9 + 7

        A = sorted(A)
        B = [1] * len(A)

        pos = {x: i for i, x in enumerate(A)}

        for i in range(len(A)):
            for j in range(i):
                if A[i] * 1.0 / A[j] not in pos:
                    continue
                B[i] += B[j] * B[pos[A[i]/A[j]]]
                B[i] %= m

        return sum(B) % m