# 823. Binary Trees With Factors

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`.

``````class Solution {
public:
int numFactoredBinaryTrees(vector<int>& A) {
long res = 0, M = 1e9 + 7;
unordered_map<int, long> dp;
sort(A.begin(), A.end());
for (int i = 0; i < A.size(); ++i) {
dp[A[i]] = 1;
for (int j = 0; j < i; ++j) {
if (A[i] % A[j] == 0 && dp.count(A[i] / A[j])) {
dp[A[i]] = (dp[A[i]] + dp[A[j]] * dp[A[i] / A[j]]) % M;
}
}
}
for (auto a : dp) res = (res + a.second) % M;
return res;
}
};
``````

Two Sum

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

https://leetcode.com/problems/binary-trees-with-factors/discuss/125794/C%2B%2BJavaPython-DP-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation