Binary Trees With Factors

Problem Statement

In this task, we are given an array of unique integers where each integer is strictly greater than 1. Our goal is to construct binary trees from these integers. Each number from the array can be used repeatedly to form multiple trees. A crucial condition for these binary trees is that each non-leaf node must be the product of its children’s values. The challenge is to determine the total number of distinct binary trees that can be constructed following these rules. Given the large possible outputs, we should return the number mod 10^9 + 7.

Examples

Example 1

Input:

arr = [2,4]

Output:

3

Explanation:

We can make these trees: `[2], [4], [4, 2, 2]`

Example 2

Input:

arr = [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]`.

Constraints

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 109
• All the values of arr are unique.

Approach and Intuition

Given the problem’s requirements, determining valid binary tree constructions can be approached by dynamically programming the solution for efficiency. The intuition behind the solution involves:

1. Utilizing memoization to store the number of ways a specific integer value can be constructed using the children nodes from the current array.

2. Iterating through each element in the array and considering it as a possible non-leaf node, and attempting to decompose it into a product of two factors which are also present in the array. This decomposing aids in recursively building sub-trees.

3. For every integer in the array:

   • Determine all possible pairs (a, b) where the product a * b equals the integer.
   • Ensure both a and b exist within the given array to satisfy the tree's construction rules.

4. For cases where an element can be represented as a product of other two elements in the array multiple times, accumulate all these possibilities to form the total count.

5. Since the number of trees can be quite large, it's essential to take all counts modulo 10^9 + 7 to keep the values manageable and within the problem’s constraints.

6. Edge cases include:

   • If the array length is 1, the only tree possible is the single node tree.
   • For larger nodes, examine each potential tree structure meticulously by evaluating each element’s divisibility within the list.

This approach leverages dynamic programming to efficiently compute possible configurations, ensuring that the problem's constraints are satisfactorily met, especially with large datasets.

Solutions

class Solution {
    public int countFactoredBinaryTrees(int[] arr) {
        int mod = 1_000_000_007;
        int len = arr.length;
        Arrays.sort(arr);
        long[] count = new long[len];
        Arrays.fill(count, 1);

        Map<Integer, Integer> indexMap = new HashMap();
        for (int i = 0; i < len; ++i)
            indexMap.put(arr[i], i);

        for (int i = 0; i < len; ++i)
            for (int j = 0; j < i; ++j) {
                if (arr[i] % arr[j] == 0) {
                    int other = arr[i] / arr[j];
                    if (indexMap.containsKey(other)) {
                        count[i] = (count[i] + count[j] * count[indexMap.get(other)]) % mod;
                    }
                }
            }

        long total = 0;
        for (long value: count) total += value;
        return (int) (total % mod);
    }
}