Leetcode 823. 요인이 있는 이진 트리 [솔루션]

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]

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:

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: