Formatted question description: https://leetcode.ca/all/823.html

823. Binary Trees With Factors (Medium)

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

Solution 1. DP

// OJ: https://leetcode.com/problems/binary-trees-with-factors/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
int numFactoredBinaryTrees(vector<int>& A) {
int mod = 1e9 + 7, N = A.size();
sort(A.begin(), A.end());
vector<long long> dp(N, 1);
unordered_map<int, long long> m;
for (int i = 0; i < N; ++i) m[A[i]] = i;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
if (A[i] % A[j] || m.find(A[i] / A[j]) == m.end()) continue;
dp[i] = (dp[i] + dp[j] * dp[m[A[i] / A[j]]]) % mod;
}
}
int ans = 0;
for (auto n : dp) ans = (ans + n) % mod;
return ans;
}
};

• class Solution {
public int numFactoredBinaryTrees(int[] A) {
final int MODULO = 1000000007;
Arrays.sort(A);
int length = A.length;
long[] counts = new long[length];
Arrays.fill(counts, 1);
Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
for (int i = 0; i < length; i++)
indexMap.put(A[i], i);
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
if (A[i] % A[j] == 0) {
int leftChild = A[j];
int rightChild = A[i] / A[j];
if (indexMap.containsKey(rightChild)) {
int rightIndex = indexMap.get(rightChild);
counts[i] = (counts[i] + counts[j] * counts[rightIndex]) % MODULO;
}
}
}
}
long trees = 0;
for (int i = 0; i < length; i++)
trees = (trees + counts[i]) % MODULO;
return (int) trees;
}
}

• // OJ: https://leetcode.com/problems/binary-trees-with-factors/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
int numFactoredBinaryTrees(vector<int>& A) {
int mod = 1e9 + 7, N = A.size();
sort(A.begin(), A.end());
vector<long long> dp(N, 1);
unordered_map<int, long long> m;
for (int i = 0; i < N; ++i) m[A[i]] = i;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
if (A[i] % A[j] || m.find(A[i] / A[j]) == m.end()) continue;
dp[i] = (dp[i] + dp[j] * dp[m[A[i] / A[j]]]) % mod;
}
}
int ans = 0;
for (auto n : dp) ans = (ans + n) % mod;
return ans;
}
};

• class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
mod = 10**9 + 7
n = len(arr)
arr.sort()
idx = {v: i for i, v in enumerate(arr)}
f = [1] * n
for i, a in enumerate(arr):
for j in range(i):
b = arr[j]
if a % b == 0 and (c := (a // b)) in idx:
f[i] = (f[i] + f[j] * f[idx[c]]) % mod
return sum(f) % mod

############

class Solution(object):
def numFactoredBinaryTrees(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
dp = {}
for i, a in enumerate(A):
dp[a] = 1
for j in range(i):
if a % A[j] == 0 and a / A[j] in dp:
dp[a] += dp[A[j]] * dp[a / A[j]]
return sum(dp.values()) % (10**9 + 7)

• func numFactoredBinaryTrees(arr []int) int {
const mod int = 1e9 + 7
sort.Ints(arr)
f := make([]int, len(arr))
for i := range f {
f[i] = 1
}
idx := map[int]int{}
for i, v := range arr {
idx[v] = i
}
for i, a := range arr {
for j := 0; j < i; j++ {
b := arr[j]
if a%b == 0 {
c := a / b
if k, ok := idx[c]; ok {
f[i] = (f[i] + f[j]*f[k]) % mod
}
}
}
}
ans := 0
for _, v := range f {
ans = (ans + v) % mod
}
return ans
}

• function numFactoredBinaryTrees(arr: number[]): number {
const mod = 10 ** 9 + 7;
arr.sort((a, b) => a - b);
const idx: Map<number, number> = new Map();
const n = arr.length;
for (let i = 0; i < n; ++i) {
idx.set(arr[i], i);
}
const f: number[] = new Array(n).fill(1);
for (let i = 0; i < n; ++i) {
const a = arr[i];
for (let j = 0; j < i; ++j) {
const b = arr[j];
if (a % b === 0) {
const c = a / b;
if (idx.has(c)) {
const k = idx.get(c)!;
f[i] = (f[i] + f[j] * f[k]) % mod;
}
}
}
}
return f.reduce((a, b) => a + b) % mod;
}