## DEV Community is a community of 642,334 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Leetcode 823. Binary Trees With Factors [Solution]

Shivam Sharma
A Fledgling innovative Web developer who aims for perfection in work. Handy with PHP, Redis, JavaScript, jQuery, CSS and HTML.

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

## Problem Statement

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

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

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:

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

C++ Code:

``````#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: