# 823. Binary Trees With Factors

## Problem Statement

<br>

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

&#x20;

**Example 1:**

<pre><code><strong>Input: arr = [2,4]
</strong><strong>Output: 3
</strong><strong>Explanation: We can make these trees: [2], [4], [4, 2, 2]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: arr = [2,4,5,10]
</strong><strong>Output: 7
</strong><strong>Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= arr.length <= 1000`
* `2 <= arr[i] <= 109`
* All the values of `arr` are **unique**.

## Intuition

```
Approach:

eg 
2 4 5 20
1 1 1 1

Each at start have one way to make a tree,
But we find extra ways to find trees in the system,

like 
for 20 -> 4,5
Number of occurences of 4,5 is 1 so 1*1 extra ways
so on we upadte extra ways for 20  
```

### Links

<https://leetcode.com/problems/binary-trees-with-factors/?envType=daily-question&envId=2023-10-26>

### Video Links

<https://www.youtube.com/watch?v=BRGz8ArRiPA&ab_channel=CodewithAlisha>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        int n= arr.size();
        sort(arr.begin(), arr.end());
        unordered_map<int,long long int> mp;

        for(auto &it: arr)
            mp[it]++;

        for(int i=0; i<n; i++){
            long long int count=0;
            for(int j=0; j<i; j++){
                if(arr[i]%arr[j] == 0){
                    int num = arr[i]/arr[j];
                    if(mp.find(num) != mp.end()){
                        count += mp[arr[j]] * mp[num];
                    }
                }
            }
            mp[arr[i]] += count;
        }

        long long int ans=0;
        for(auto &it: mp){
            ans += it.second;
        }

        return ans % int(1e9+7);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###