[Leetcode] Problem 823 - Binary Trees With Factors

Posted on | In ,

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

No.1

Input: A = [2, 4]

Output: 3

Explanation: We can make these trees: [2], [4], [4, 2, 2]

No.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. 1 <= A.length <= 1000.
  2. 2 <= A[i] <= 10 ^ 9.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// dp[c]: number of trees rooted at c
// dp[c] = sum(dp[a] * dp[b]), c = a * b, a,b,c in A
// ans = sum(dp[c]), c in A
public int numFactoredBinaryTrees(int[] A) {
    long result = 0;
    long mod = (long) 1e9 + 7;
    Map<Integer, Long> dp = new HashMap<>();
    
    Arrays.sort(A);

    for (int i = 0; i < A.length; i++) {
        dp.put(A[i], 1L);

        for (int j = 0; j < i; j++) {
            if (A[i] % A[j] == 0 && dp.containsKey(A[i] / A[j]))
                dp.replace(A[i], (dp.get(A[i]) + dp.get(A[j]) * dp.get(A[i] / A[j])) % mod);
        }

        result = (result + dp.get(A[i])) % mod;
    }

    return (int) result;
}