LeetCode: Binary Trees With Factors

Posted on May 18, 2018July 26, 2020 by braindenny

Binary Trees With Factors

Similar Problems:

Given an array of unique integers, each integer 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 it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/binary-trees-with-factors
// Basic Ideas: dynamic programming
//
//  Root node as i
//
//    dp(i) = dp(k)*dp(i-k)
//         Both k and i-k should exist in the original array
//         Then add 1 as a single node in the tree
// Complexity: Time O(n^2) Space O(n)
import ("math"
        "sort")
func numFactoredBinaryTrees(A []int) int {
    sort.Ints(A)
    mod := int(math.Pow(10, 9)+7)
    dp := map[int]int{}
    for _, v := range A {
        dp[v] = 1
    }
    for i:=0; i<len(A); i++ {
        for k:=i-1; k>=0; k-- {
            if A[i]%A[k] == 0 {
                v := A[i]/A[k]
                if _, ok := dp[v]; ok {
                    dp[A[i]] = dp[A[i]] + dp[A[k]]*dp[v]
                }
            }
        }
    }
    res := 0
    for _, v := range dp {
        res = (res+v)%mod
    }
    return res
}

Post Views: 5