Problem

Given an array of unique integers, arr, where each integer arr[i] 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 its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10^9 + 7.

Examples

Example 1:

1
2
3

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: `[2], [4], [4, 2, 2]`

Example 2:

1
2
3

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]`.

Solution

Method 1 - Using DP

Here is the approach:

  1. Sorting Input: First, sort the array to process smaller values first.
  2. Dynamic Programming: Use a hashmap (dp) where dp[x] represents the number of binary trees with root value x. Initially, each integer is considered to have one tree where the integer itself is the root node (leaf tree).
  3. Traversal: Iterate through each value in the array and calculate the number of trees it can represent as roots:
    • For each integer x, loop through every possible left child l (where l divides x evenly).
    • Calculate the right child (r) as x / l.
    • If both l and r exist in the array, multiply the count of trees rooted at l and r, then add this count to dp[x].
  4. Result: Sum all values in dp modulo (10^9 + 7).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        arr.sort()
        dp = {}
        ans = 0
        
        for x in arr:
            dp[x] = 1  # Initial tree with root x itself
            for l in arr:
                if l >= x:  # Break early as we only need values smaller than x
                    break
                if x % l == 0:
                    r = x // l
                    if r in dp:
                        dp[x] += dp[l] * dp[r]
                        dp[x] %= MOD
            
            ans = (ans + dp[x]) % MOD
        
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        int MOD = 1_000_000_007;
        Arrays.sort(arr);
        Map<Integer, Long> dp = new HashMap<>();
        long ans = 0;

        for (int x : arr) {
            dp.put(x, 1L);  // Initial tree with root value x itself
            for (int l : arr) {
                if (l >= x) { // Break early for efficiency
                    break;
                }
                if (x % l == 0) {
                    int r = x / l;
                    if (dp.containsKey(r)) {
                        dp.put(x, dp.get(x) + dp.get(l) * dp.get(r));
                        dp.put(x, dp.get(x) % MOD);
                    }
                }
            }
            ans = (ans + dp.get(x)) % MOD;
        }

        return (int) ans;
    }
}

Complexity

  • Time: O((n^2 + n log n), where n is the size of the array.
    • O(n log n) for sorting.
    • O(n^2) for nested loops, since for each value we loop through possible left children.
  • Space: O(n) for dp hashmap.