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 10⁹ + 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] <= 10⁹
All the values of arr are unique.

Solution:

Firstly let us sort the array and store the values of the array in a (value, index) hashmap amap. Now let us find the answer dp[i] for the subarray ending at index i. Later we can sum up all values in dp array to get the final answer. We can quickly see that

 
dp[i] = 1 + sum(dp[j]*dp[k])

where j, k are chosen such that arr[j]*arr[k] = arr[i]. We have an extra one for the singleton tree [a[i]]. We can write this into following solution:

 
class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) 
    {
        int n = arr.size(), mod = 1000000007, res=0;
        sort(arr.begin(), arr.end());
        unordered_map<int,int> amap;
        for(int i=0;i<n;i++)amap[arr[i]] = i;
        vector<long> dp(n);
        for (int i=0; i<n; i++)
        {
            dp[i] = 1;
            for (int j=0; j<i; j++) if (arr[i]%arr[j]==0 && amap.count(arr[i]/arr[j])) 
                dp[i] += dp[j] * dp[amap[arr[i]/arr[j]]] % mod;
            dp[i]%= mod;
            res += dp[i];
            res %= mod;
        }
        return res;
    }
};

 
TC: O(n^2)
SC: O(n)