Leetcode 823. Binary Trees With Factors [Solution]

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
• Explanation
• Solution
• Implementation

Problem Statement

Question: 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

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: