> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/801-900/binary-trees-with-factors.md).

# 823. Binary Trees With Factors

### Description

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

### Constraints

* `1 <= arr.length <= 1000`
* `2 <= arr[i] <= 109`

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/binary-trees-with-factors/)
* ProgramCreek
* [YouTube](https://youtu.be/9UrDjy2HtZ8)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** arr = \[2, 4]

**Output:** 3

**Explanation:** We can make these trees: \[2], \[4], \[4, 2, 2]
{% endtab %}

{% tab title="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].
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N^2), where N is the length of arr. 
 *    This comes from the two for-loops iterating i and j.
 * Space complexity : O(N), the space used by map.
 */

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        if(arr == null || arr.length == 0) {
            return 0;
        }
        Arrays.sort(arr);
        
        Map<Integer, Long> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++) {
            long count = 1;
            for(int j = 0; j < i; j++) {
                if(arr[i]%arr[j] == 0 && map.containsKey(arr[i]/arr[j])) {
                    count += map.get(arr[j]) * map.get(arr[i]/arr[j]);
                }
            }
            map.put(arr[i], count);
        }
        
        long totalCount = 0;
        for(long value: map.values()) {
            totalCount += value;
        }
        
        return (int) (totalCount % 1000000007);
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*