## Monday, May 14, 2018

### LeetCode 823 - Binary Trees With Factors

https://leetcode.com/problems/binary-trees-with-factors/description/
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.

The largest value v used must be the root node in the tree. Say dp(v) is the number of ways to make a tree with root node v.
If the root node of the tree (with value v) has children with values x and y (and x * y == v), then there are dp(x) * dp(y) ways to make this tree.
In total, there are $\sum _{\begin{array}{c}x\ast y=v\end{array}}\text{dp}\left(x\right)\ast \text{dp}\left(y\right)$ ways to make a tree with root node v.
Algorithm
Actually, let dp[i] be the number of ways to have a root node with value A[i].
Since in the above example we always have x < v and y < v, we can calculate the values of dp[i] in increasing order using dynamic programming.
For some root value A[i], let's try to find candidates for the children with values A[j] and A[i] / A[j] (so that evidently A[j] * (A[i] / A[j]) = A[i]). To do this quickly, we will need index which looks up this value: if A[k] = A[i] / A[j], then index[A[i] / A[j]] = k.
After, we'll add all possible dp[j] * dp[k] (with j < i, k < i) to our answer dp[i]. In our Java implementation, we carefully used long so avoid overflow issues.
    public int numFactoredBinaryTrees(int[] A) {
int MOD = 1_000_000_007;
int N = A.length;
Arrays.sort(A);
long[] dp = new long[N];
Arrays.fill(dp, 1);

Map<Integer, Integer> index = new HashMap();//
for (int i = 0; i < N; ++i)
index.put(A[i], i);

for (int i = 0; i < N; ++i)
for (int j = 0; j < i; ++j) {
if (A[i] % A[j] == 0) { // A[j] is left child
int right = A[i] / A[j];
if (index.containsKey(right)) {
dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
}
}
}

long ans = 0;
for (long x: dp) ans += x;
return (int) (ans % MOD);
}
https://www.jianshu.com/p/d861251c2ec3

dp[tmp] = dp[i] * dp[j] * 2 (i != j)
dp[tmp] = dp[i] * dp[j] (i == j)

Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].
dp[i] = sum(dp[j] * dp[i/j]),  0 <= j < i, A[i] is a factor of A[j] and A[i] / A[j] also in A.
ans = sum(dp[i]), for all possible i.

https://leetcode.com/problems/binary-trees-with-factors/discuss/125794/C++JavaPython-DP-solution
    public int numFactoredBinarydps(int[] A) {
long res = 0L, mod = (long) Math.pow(10, 9) + 7;
Arrays.sort(A);
HashMap<Integer, Long> dp = new HashMap<>();
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.put(A[i], (dp.get(A[i]) + dp.get(A[j]) * dp.get(A[i] / A[j])) % mod);
}
for (long v : dp.values()) res = (res + v) % mod;
return (int) res;
}`
https://leetcode.com/problems/binary-trees-with-factors/discuss/125815/Java-accepted-solution