Code Implementation

class Solution:
    def numFactoredBinaryTrees(self, arr):
        MOD = 10 ** 9 + 7
        arr.sort()
        dp = {}
        index = {x: i for i, x in enumerate(arr)}
        for i, x in enumerate(arr):
            dp[x] = 1
            for j in range(i):
                if x % arr[j] == 0:
                    right = x // arr[j]
                    if right in dp:
                        dp[x] += dp[arr[j]] * dp[right]
            dp[x] %= MOD
        return sum(dp.values()) % MOD
      

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

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        int MOD = 1_000_000_007;
        Arrays.sort(arr);
        Map<Integer, Long> dp = new HashMap<>();
        for (int i = 0; i < arr.length; ++i) {
            dp.put(arr[i], 1L);
            for (int j = 0; j < i; ++j) {
                if (arr[i] % arr[j] == 0) {
                    int right = arr[i] / arr[j];
                    if (dp.containsKey(right)) {
                        dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(right)) % MOD);
                    }
                }
            }
        }
        long res = 0;
        for (long v : dp.values()) res = (res + v) % MOD;
        return (int)res;
    }
}
      

var numFactoredBinaryTrees = function(arr) {
    const MOD = 1e9 + 7;
    arr.sort((a, b) => a - b);
    const dp = new Map();
    for (let i = 0; i < arr.length; ++i) {
        dp.set(arr[i], 1);
        for (let j = 0; j < i; ++j) {
            if (arr[i] % arr[j] === 0) {
                let right = arr[i] / arr[j];
                if (dp.has(right)) {
                    dp.set(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(right)) % MOD);
                }
            }
        }
    }
    let res = 0;
    for (let v of dp.values()) res = (res + v) % MOD;
    return res;
};
      

Problem Description

Given an array arr of unique positive integers, consider binary trees where each non-leaf node's value is the product of its two children's values, and each node's value must be in arr. Each integer from arr can be used multiple times in different trees or positions. The task is to count the number of possible binary trees that can be built, where the value of each node is from arr and for every non-leaf node, its value equals the product of its two children (both from arr). Return the count modulo 10⁹+7.

• Each tree must use only values from arr.
• Each node's value can be reused in different trees and positions.
• Order of children matters (trees with left/right swapped are different).
• Return the total number of such trees modulo 10⁹+7.

Thought Process

At first, you might think about brute-forcing all possible tree structures, recursively trying to pair every possible combination of left and right children for each value. However, this quickly becomes infeasible as the number of possible trees grows exponentially with the size of arr.

To optimize, notice that for each value x in arr, you can build trees with x as the root by finding all pairs of values (a, b) in arr such that a * b == x. For each such pair, the number of ways to build a tree with a as the left child and b as the right child is the product of the number of trees rooted at a and the number rooted at b.

This suggests a dynamic programming approach: for each value, store the number of trees that can be built with it as the root, and build up from the smallest to the largest values.

Solution Approach

We use dynamic programming to efficiently count the number of binary trees for each value in arr. Here’s how:

1. Sort arr in ascending order so we can build up solutions from smaller factors.
2. Use a hash map (dictionary) dp where dp[x] stores the number of binary trees with root x.
3. For each value x in arr:
   • Initialize dp[x] = 1 (a single node tree).
   • For every smaller value a in arr (where a < x):
     • If x % a == 0, then b = x / a is a potential right child.
     • If b is in arr, then a and b can be children of x.
     • Add dp[a] * dp[b] to dp[x] (since left and right subtrees are independent).
   • Take modulo 10⁹+7 at each step to avoid overflow.
4. Sum dp[x] for all x in arr for the final answer.

We use a hash map for dp so that lookups and updates are O(1). Sorting ensures we only consider smaller factors first, so all needed subproblem results are already computed.

Example Walkthrough

Let's take arr = [2, 4, 5, 10].

• For 2: Only possible tree is a single node (2 itself), so dp[2] = 1.
• For 4:
  • Possible pairs: (2,2) since 2*2=4 and both 2s are in arr.
  • So, dp[4] = 1 (single node) + dp[2]*dp[2] = 1+1=2.
• For 5: No pairs multiply to 5, so dp[5] = 1.
• For 10:
  • Possible pairs: (2,5) and (5,2) since 2*5=10 and 5*2=10.
  • So, dp[10] = 1 (single node) + dp[2]*dp[5] + dp[5]*dp[2] = 1+1+1=3.
• Total: 1 (2) + 2 (4) + 1 (5) + 3 (10) = 7 possible trees.

This matches the expected output for this input.

Time and Space Complexity

• Brute-force: Exponential time, as it tries all possible tree structures and combinations, which is infeasible for even moderate input sizes.
• Optimized (DP) Approach:
  • For each element x in arr, we check all smaller elements as possible left children. For each, we do O(1) work (lookup and multiplication).
  • The outer loop is O(n), and the inner loop is also O(n), so total is O(n²), where n is the length of arr.
  • Sorting the array is O(n log n), which is dominated by O(n²).
  • Space complexity is O(n) for the dp map.

Summary

The key insight is to recognize the subproblem structure: the number of trees for a value depends on the number of trees for its possible factors. By sorting the array and using dynamic programming, we efficiently build up the answer for each value, ensuring all required sub-results are available when needed. This approach reduces the problem from exponential to quadratic time, making it feasible for large inputs. The solution is elegant because it leverages the properties of binary trees and factorization, and uses memoization to avoid redundant computation.