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

*


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-snippets.hbamithkumara.com/leetcode/problems/801-900/binary-trees-with-factors.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.