843. Binary Trees With Factors

• Difficulty: Medium

• Topics:

• Similar Questions:

Problem:

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.

Solutions:

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        sort(A.begin(), A.end());
        map<int, long> dp;

        long ret = 0;

        for (int i = 0; i < A.size(); ++i) {
            dp[A[i]] = 1;
            for (auto it = dp.begin(); it != dp.end(); ++it) {
                if (A[i] % it->first == 0 && dp.count(A[i]/it->first)) {
                    dp[A[i]] = (dp[A[i]] + it->second * dp[A[i]/it->first]) % MOD;
                }
            }
            ret = (ret + dp[A[i]]) % MOD;
        }

        return ret;
    }

private:
    int MOD = 1e9 + 7;

};