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;
    }
};

Java

  • 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(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)
    

All Problems

All Solutions