# Binary Trees With Factors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-trees-with-factors)
Canonical: https://scaleengineer.com/dsa/problems/binary-trees-with-factors
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## 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** `109 + 7`.

**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**.

# Approaches
## Brute-Force Recursion
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.
**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, ...]`).
**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`.
### Explanation
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)`:
1.  Initialize a counter `count` to 1, representing the tree with only the `root` node.
2.  Iterate through each number `factor1` in the input array `arr`.
3.  If `root` is divisible by `factor1`, calculate `factor2 = root / factor1`.
4.  Check if `factor2` also exists in the `HashSet` of array elements.
5.  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`.
6.  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.

```java
// Note: This solution is for demonstration and will cause Time Limit Exceeded.
import java.util.HashSet;
import java.util.Set;

class Solution {
    private Set<Integer> numSet;
    private int[] arr;
    private long MOD = 1_000_000_007;

    public int numFactoredBinaryTrees(int[] arr) {
        this.arr = arr;
        this.numSet = new HashSet<>();
        for (int x : arr) {
            numSet.add(x);
        }

        long totalTrees = 0;
        for (int num : arr) {
            totalTrees = (totalTrees + countTrees(num)) % MOD;
        }
        return (int) totalTrees;
    }

    private long countTrees(int root) {
        long count = 1; // The tree with just the root
        for (int factor1 : arr) {
            if (root > factor1 && root % factor1 == 0) {
                int factor2 = root / factor1;
                if (numSet.contains(factor2)) {
                    long ways1 = countTrees(factor1);
                    long ways2 = countTrees(factor2);
                    count = (count + (ways1 * ways2)) % MOD;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Create a `HashSet` from the input `arr` for O(1) average time lookups.
2. Initialize `totalTrees = 0`.
3. For each `num` in `arr`:
    a. Add the result of a recursive function `countTrees(num)` to `totalTrees` (modulo `10^9 + 7`).
4. Return `totalTrees`.

**`countTrees(root)` function:**
1. Initialize `count = 1` (for the leaf node).
2. 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`).
3. Return `count`.

## Dynamic Programming (Bottom-Up)
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.
**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.
**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.
### Explanation
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]`:
1.  We initialize a `count` for `num` to 1. This represents the base case: a tree consisting of only the leaf node `num`.
2.  We then search for pairs of factors. We iterate through the previously processed numbers `factor1 = arr[j]` (where `j < i`).
3.  If `num` is divisible by `factor1`, we find the other factor, `factor2 = num / factor1`.
4.  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`.
5.  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`.
6.  After checking all possible `factor1`s, 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`.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        long MOD = 1_000_000_007;
        int n = arr.length;
        Arrays.sort(arr);

        Map<Integer, Long> dp = new HashMap<>();
        long totalTrees = 0;

        for (int i = 0; i < n; i++) {
            int root = arr[i];
            long count = 1L; // Base case: the node itself is a tree

            for (int j = 0; j < i; j++) {
                int factor1 = arr[j];
                if (root % factor1 == 0) {
                    int factor2 = root / factor1;
                    if (dp.containsKey(factor2)) {
                        long ways1 = dp.get(factor1);
                        long ways2 = dp.get(factor2);
                        count = (count + (ways1 * ways2)) % MOD;
                    }
                }
            }
            dp.put(root, count);
            totalTrees = (totalTrees + count) % MOD;
        }

        return (int) totalTrees;
    }
}
```
### Algorithm
1. Define `MOD = 10^9 + 7`.
2. Sort the input array `arr` in ascending order.
3. Create a `HashMap<Integer, Long> dp` to store the number of trees for each root value.
4. Initialize `totalTrees = 0`.
5. 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`.
6. Return `totalTrees` as an integer.

# Solutions
### Java

```java
class 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 ; } }
```

### Python

```python
class Solution:
    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

```

### CPP

```cpp
class Solution {
public:
  int numFactoredBinaryTrees(vector<int> &arr) {
    const int mod = 1e9 + 7;
    sort(arr.begin(), arr.end());
    unordered_map<int, int> idx;
    int n = arr.size();
    for (int i = 0; i < n; ++i) {
      idx[arr[i]] = i;
    }
    vector<long> f(n, 1);
    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.count(c)) {
            int k = idx[c];
            f[i] = (f[i] + 1l * f[j] * f[k]) % mod;
          }
        }
      }
    }
    long ans = 0;
    for (long v : f) {
      ans = (ans + v) % mod;
    }
    return ans;
  }
};

```