Leetcode 823. Binary Trees With Factors [Solution]
Tags: algorithms, cpp, programming, tutorial
Published: 2021-03-13 15:37:56

This question checks your knowledge about **Dynamic Programming** and permutation-combination. I am also a beginner and I had to look for the answer online to understand it but once you understand it, It helps in understanding many such questions in the future.

**Difficulty:** Medium
**Jump To:**
* [Problem Statement](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>

**Question:** [https://leetcode.com/problems/binary-trees-with-factors/](https://leetcode.com/problems/binary-trees-with-factors/)


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`

---

## Explanation <a name="explanation"></a>
First, we need to understand, what is a factor to a number. For a number `n`, `x` is a factor if `n%x==0` so two numbers `x` and `y` can be children of `n` in the binary tree, only if `x * y = n`.

One small point to bring into notice: It's given that `2 <= arr[i]`because if `arr[i]` is `0` or `1` then infinite solutions are possible.

So we need to find that how many such trees of any depth can be created using a given number in any quantity. for example, if given numbers are `[2,4,5,10]` then `7` trees are possible as below:

```
[2]           [4]           [5]           [10]

     [4]              [10]              [10]
    /   \            /    \            /    \
  [2]   [2]        [5]    [2]        [2]    [5]
```

---

## Solution <a name="solution"></a>

We need to see this problem as a problem breakable into subproblems, like in the example `[2,5,10,20]` we can see this problem broken into subproblems `[2]`, `[2,5]`, `[2,5,10]` and then final problem `[2,5,10,20]`.  We will solve these subproblems in order and by finding the number of trees with an item as root which is just added in the current subproblem in comparison to the last subproblem i.e. 
1. We'll first find the number of trees with `2` as a root and no children options available i.e. `1`.
2. Then the number of trees with `5` as a root and `[2]` is available as children option i.e. `1`.
3. Then the number of trees with `10` as a root and `[2,5]` is available as children option i.e. `3`.
4. Then the number of trees with `20` as a root and `[2,5,10]` is available as children option i.e. `7`.

All the trees possible are as below:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iybl0tudzy1mrqt8r89h.png)

In the end, we'll just sum up all the above number of trees to get the solution to the problem. This should be clear now that we'll be using dynamic programming.

To get the answer for each subproblem we are using the logic that `1` tree is possible with just that element to let's say `n` which is a tree with the only root. And for each element which is a factor of `n` let's say `x`(and another one is `y`) we'll add multiplication of subsolution of `x` and subsolution of `y`. Once `x` as a left child and then `y` as a left child. As factors will always be smaller than the actual number so we'll sort the array first so that we don't need to find factors in the whole array every time, we'll just see the elements before the current number is sorted array.

**DP Equation:**
```
dp[i] = sum(dp[j] * dp[i / j]) 
ans = sum(dp[i])
```

Let's see the code, it'll clear things more.


---

## Implementation <a name="implementation"></a>

**C++ Code:**
```cpp
#define MOD 1000000007
class Solution {
public:
	int numFactoredBinaryTrees(vector<int>& arr) {
		unordered_map<int,long int> dp;
		int len=arr.size();

		// Sorting array
		sort(arr.begin(), arr.end());

		for(int i=0;i<len;i++){
			// One tree is always possible (root only)
			dp[arr[i]] = 1;

			// Check for all elements less than current element arr[i]
			for(int j=0; j<i; j++){
				// Check if arr[j] is factor of arr[i] 
				// and the second factor (arr[i]/arr[j]) is seen
				if(arr[i]%arr[j]==0 && dp.find((arr[i]/arr[j]))!=dp.end()){
					// Add combinations in dp with arr[j] as left child
					// So (arr[i]/arr[j]) becomes right child automatically
					dp[arr[i]] += (dp[arr[j]] * dp[(arr[i]/arr[j])]) % MOD;
					dp[arr[i]] %= MOD;
				}
			}
		}
		
		int ans=0;
		// Find sum of dp to sum solution of all subproblems
		for(auto i : dp){
			ans += i.second;
			ans %= MOD;
		}
		return ans;
	}
};
```

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


**Runnable C++ code:**

{% replit @shivams136/Leetcode-823-Binary-Trees-With-Factors %}