Binary Trees With Factors

Med

#0777Time: Exponential, likely O(N^N) or worse. The number of recursive calls grows very rapidly without memoization, as each call can spawn `O(N)` new pairs of recursive calls.Space: O(N), where N is the length of `arr`. This is for the recursion stack depth in the worst case (e.g., for an input like `[2, 4, 8, 16, ...]`).

Patterns

Dynamic Programming

Algorithms

Sorting

Data structures

Array Hash Table

Prompt

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⁹ + 7.

Example 1:

[2], [4], [4, 2, 2]

Example 2:

[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a plain recursive function to count the number of trees for each number in the input array. For each number x, we consider it as a root. The number of trees with root x is 1 (for the leaf node) plus the sum of products of the number of trees for its possible children. We find pairs of factors (y, z) of x that are also present in the input array. The number of ways to form a tree with x as the root and y, z as children is the product of the number of ways to form trees with root y and root z. This method does not use memoization, leading to re-computation of results for the same subproblems.

Algorithm

Create a HashSet from the input arr for O(1) average time lookups.
Initialize totalTrees = 0.
For each num in arr: a. Add the result of a recursive function countTrees(num) to totalTrees (modulo 10^9 + 7).
Return totalTrees.

countTrees(root) function:

Initialize count = 1 (for the leaf node).
For each factor1 in arr: a. If root is divisible by factor1: i. Let factor2 = root / factor1. ii. If factor2 is in the HashSet: - Recursively call countTrees(factor1) and countTrees(factor2). - Add the product of their results to count (modulo 10^9 + 7).
Return count.

Walkthrough

We define a recursive function, say countTrees(root), which calculates the number of possible binary trees with the given root value. To make checking for the existence of factors efficient, we first put all elements of arr into a HashSet.

The main function iterates through each number in arr and calls countTrees for it, summing up the results modulo 10^9 + 7.

Inside countTrees(root):

Initialize a counter count to 1, representing the tree with only the root node.
Iterate through each number factor1 in the input array arr.
If root is divisible by factor1, calculate factor2 = root / factor1.
Check if factor2 also exists in the HashSet of array elements.
If it exists, it means we found a valid pair of children. We recursively call countTrees(factor1) and countTrees(factor2) and add their product to our count.
Return the final count.

This approach is very slow because it recomputes the results for the same subproblems multiple times. For example, countTrees(2) would be calculated repeatedly whenever 2 appears as a factor in the recursion tree.

1// Note: This solution is for demonstration and will cause Time Limit Exceeded.2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    private Set<Integer> numSet;7    private int[] arr;8    private long MOD = 1_000_000_007;9 10    public int numFactoredBinaryTrees(int[] arr) {11        this.arr = arr;12        this.numSet = new HashSet<>();13        for (int x : arr) {14            numSet.add(x);15        }16 17        long totalTrees = 0;18        for (int num : arr) {19            totalTrees = (totalTrees + countTrees(num)) % MOD;20        }21        return (int) totalTrees;22    }23 24    private long countTrees(int root) {25        long count = 1; // The tree with just the root26        for (int factor1 : arr) {27            if (root > factor1 && root % factor1 == 0) {28                int factor2 = root / factor1;29                if (numSet.contains(factor2)) {30                    long ways1 = countTrees(factor1);31                    long ways2 = countTrees(factor2);32                    count = (count + (ways1 * ways2)) % MOD;33                }34            }35        }36        return count;37    }38}

Complexity

Time

Exponential, likely O(N^N) or worse. The number of recursive calls grows very rapidly without memoization, as each call can spawn `O(N)` new pairs of recursive calls.

Space

O(N), where N is the length of `arr`. This is for the recursion stack depth in the worst case (e.g., for an input like `[2, 4, 8, 16, ...]`).

Trade-offs

Pros

Simple to conceptualize as it directly translates the problem's recursive structure.

Cons

Extremely inefficient due to massive redundant computations.
Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.
The recursion depth can be large, potentially leading to a StackOverflowError.

This is an efficient approach that avoids recomputing results by storing them using dynamic programming. The core idea is that the number of trees with root x can be calculated if we already know the number of trees for all of x's factors that are present in the input array. By sorting the input array, we guarantee that when we process a number, we have already computed and stored the results for all its smaller factors.

Algorithm

Define MOD = 10^9 + 7.
Sort the input array arr in ascending order.
Create a HashMap<Integer, Long> dp to store the number of trees for each root value.
Initialize totalTrees = 0.
For i from 0 to arr.length - 1: a. Let num = arr[i]. b. Initialize a local count = 1L (for the tree with a single node num). c. For j from 0 to i - 1: i. Let factor1 = arr[j]. ii. If num % factor1 == 0: - Let factor2 = num / factor1. - If dp contains factor2 as a key: - count = (count + dp.get(factor1) * dp.get(factor2)) % MOD. d. Put the final count into the map: dp.put(num, count). e. Add count to totalTrees: totalTrees = (totalTrees + count) % MOD.
Return totalTrees as an integer.

Walkthrough

First, we sort the input array arr in ascending order. This ensures that for any number arr[i], any of its factors that are also in arr must appear before it (i.e., at an index j < i).

We use a HashMap, let's call it dp, to store the number of trees that can be formed with each number as the root. The key is the number from arr, and the value is the count of trees.

We iterate through the sorted array. For each number num = arr[i]:

We initialize a count for num to 1. This represents the base case: a tree consisting of only the leaf node num.
We then search for pairs of factors. We iterate through the previously processed numbers factor1 = arr[j] (where j < i).
If num is divisible by factor1, we find the other factor, factor2 = num / factor1.
We check if factor2 also exists in our dp map. Since the array is sorted, if factor2 exists in arr, it must have been processed already and will be in dp.
If factor2 is in dp, we've found a valid pair of children. The number of new trees we can form is dp.get(factor1) * dp.get(factor2). We add this product to our count.
After checking all possible factor1s, we store the final count in our map: dp.put(num, count).

The total number of trees is the sum of all values in the dp map. We keep a running total, updated in each step of the outer loop, to avoid a final summation loop. All additions and multiplications are performed modulo 10^9 + 7.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int numFactoredBinaryTrees(int[] arr) {7        long MOD = 1_000_000_007;8        int n = arr.length;9        Arrays.sort(arr);10 11        Map<Integer, Long> dp = new HashMap<>();12        long totalTrees = 0;13 14        for (int i = 0; i < n; i++) {15            int root = arr[i];16            long count = 1L; // Base case: the node itself is a tree17 18            for (int j = 0; j < i; j++) {19                int factor1 = arr[j];20                if (root % factor1 == 0) {21                    int factor2 = root / factor1;22                    if (dp.containsKey(factor2)) {23                        long ways1 = dp.get(factor1);24                        long ways2 = dp.get(factor2);25                        count = (count + (ways1 * ways2)) % MOD;26                    }27                }28            }29            dp.put(root, count);30            totalTrees = (totalTrees + count) % MOD;31        }32 33        return (int) totalTrees;34    }35}

Complexity

Time

O(N^2), where N is the length of `arr`. Sorting the array takes `O(N log N)`. The dominant part is the nested loop structure. The outer loop runs N times, and the inner loop runs up to N times in the worst case.

Space

O(N), where N is the length of `arr`. This space is used to store the `dp` map which holds an entry for each number in the input array.

Trade-offs

Pros

Highly efficient and guaranteed to pass within the time limits.
Avoids recursion overhead and potential stack overflow issues.
The logic is clear and builds the solution from smaller subproblems to larger ones.

Cons

The O(N^2) time complexity might be a concern for much larger constraints, but it is efficient enough for the given problem size.

Solutions

Solution

1class Solution { public int numFactoredBinaryTrees ( int [] arr ) { final int mod = ( int ) 1 e9 + 7 ; Arrays . sort ( arr ); int n = arr . length ; long [] f = new long [ n ]; Arrays . fill ( f , 1 ); Map < Integer , Integer > idx = new HashMap <>( n ); for ( int i = 0 ; i < n ; ++ i ) { idx . put ( arr [ i ], i ); } for ( int i = 0 ; i < n ; ++ i ) { int a = arr [ i ]; for ( int j = 0 ; j < i ; ++ j ) { int b = arr [ j ]; if ( a % b == 0 ) { int c = a / b ; if ( idx . containsKey ( c )) { int k = idx . get ( c ); f [ i ] = ( f [ i ] + f [ j ] * f [ k ]) % mod ; } } } } long ans = 0 ; for ( long v : f ) { ans = ( ans + v ) % mod ; } return ( int ) ans ; } }

1class Solution:2    def numFactoredBinaryTrees(self, arr: List[int]) -> int: mod = 10 ** 9 + 7 n = len(arr) arr . sort() idx = {v: i for i, v in enumerate(arr)} f = [1] * n for i, a in enumerate(arr): for j in range(i): b = arr[j] if a % b == 0 and (c: = (a // b)) in idx: f[i] = (f[i] + f[j] * f[idx[c]]) % mod return sum(f) % mod

1class Solution {2public:3  int numFactoredBinaryTrees(vector<int> &arr) {4    const int mod = 1e9 + 7;5    sort(arr.begin(), arr.end());6    unordered_map<int, int> idx;7    int n = arr.size();8    for (int i = 0; i < n; ++i) {9      idx[arr[i]] = i;10    }11    vector<long> f(n, 1);12    for (int i = 0; i < n; ++i) {13      int a = arr[i];14      for (int j = 0; j < i; ++j) {15        int b = arr[j];16        if (a % b == 0) {17          int c = a / b;18          if (idx.count(c)) {19            int k = idx[c];20            f[i] = (f[i] + 1l * f[j] * f[k]) % mod;21          }22        }23      }24    }25    long ans = 0;26    for (long v : f) {27      ans = (ans + v) % mod;28    }29    return ans;30  }31};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem