23.10.27 Today’s Leetcode

823. Binary Trees With Factors

DFS, with DP

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:

        sorted(arr)
        MOD = 10 ** 9 + 7
        check_set = set(arr)

        dp = {}
        def dfs(cur):
            if cur in dp:
                return dp[cur]  
            if cur not in check_set:
                return 0

            nonlocal arr
            res = 1
            for i in arr:
                if cur == i:
                    continue
                if cur % i == 0:
                    res += dfs(i) * dfs(cur // i)
            dp[cur] = res
            return res

        temp = 0
        for i in arr:
            temp += dfs(i)
            temp %= MOD

        # print(dp)
        
        return temp

DFS with memoization

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        arr.sort()
        # increasing order sorting
        # [2, 3, 9, 18]
        
        dp = [1] * len(arr)
        index = {x: i for i, x in enumerate(arr)}
        # value -> index mapping

        for i, x in enumerate(arr):
            for j in range(i):
                if x % arr[j] == 0:
                    ryt = x / arr[j]
                    if ryt in index:
                        dp[i] += dp[j] * dp[index[ryt]]
                        dp[i] %= MOD
        
        return sum(dp) % MOD