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, where:

• The value of each non-leaf node is equal to the product of the values of its children.
• Each leaf node has a value equal to itself.
• 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, 5], [20, 2, 5]

Approach:

In this problem we are given an array of integers which will represent the values of the nodes of our resultant binary trees. We have to find the number of such trees which can be formed using the given nodes as leaves.

Let's take an example and try to generalise our approach. Suppose we are given the input arr = [2, 4], and we have to make binary trees using these values as the leaves. Then the possible binary trees which can be formed are:

• [2]: A tree with only one node which is value 2.
• [4]: A tree with only one node which is value 4.
• [4, 2, 2]: A tree with one parent node which is 4 and it's left and right children values are 2 and 2 respectively.

Now, let's observe some patterns from the above examples. If we select a particular node as the parent node, then the descendants of that node should be derived from the input array itself. Now, if the parent node has a value of x, we need to identify two numbers p and q, such that p*q = x. Then we need to check if p and q are already present in the given input array, as they will be the children of our parent node.

Hence, for every node, we will iterate through all its possible divisors and check if they are available in the input array. If they are present, we will calculate the number of trees possible using those children nodes recursively. We will then add up the result from all such pairs of children of the current node.

In this way, we can obtain the number of trees possible for each node and sum up the result to get the final answer.

Algorithm:

1. Sort the given array in increasing order.
2. Initialize a dictionary to store the intermediate results.
3. Iterate through each element of the input array and for each element, initialize a variable 'count' to 1.
4. For each element, we iterate through all its possible divisors i and j such that i*j = element.
5. If i and j are present in the input array, we obtain the number of trees possible using these two nodes recursively.
6. We then multiply the number of trees obtained from these two nodes and add it to the count variable.
7. Store this count in the dictionary along with the current node as the key.
8. Finally, we iterate through the values of the dictionary and add them up to obtain the final answer.

Let's see the implementation of the above algorithm.

Code:

def numFactoredBinaryTrees(arr): MOD = 1000000007 arr.sort() N = len(arr) dp = {} for i in range(N): count = 1 for j in range(i): if arr[i] % arr[j] == 0 and (arr[i] // arr[j]) in dp: count += dp[arr[j]] * dp[arr[i] // arr[j]] dp[arr[i]] = count return sum(dp.values()) % MOD

testing the function

print(numFactoredBinaryTrees([2, 4])) print(numFactoredBinaryTrees([2, 4, 5, 10]))

Output

3

7

Time complexity: O(n^2), as we are iterating through all possible pairs of nodes for each node.

Space complexity: O(n), a dictionary is used to store the intermediate results.

1