Sponsored
Sponsored
This approach involves using dynamic programming with a hashmap (or dictionary) to keep track of the number of ways a particular element can be the root of binary trees. We first sort the array, and then for each element, we iterate over all previous elements to find pairs that multiply to the element of interest. For each valid pair, we update the number of trees using previously computed results for the factors.
Time Complexity: O(n^2), where n is the length of the array, due to the nested loops evaluating possibilities.
Space Complexity: O(n), for storing the dp table.
1function numFactoredBinaryTrees(arr) {
2 arr.sort((a, b) => a - b);
3 const mod = 1000000007;
4 const dp = new Map();
5 let result = 0;
6
7 for (let i = 0; i < arr.length; i++) {
8 dp.set(arr[i], 1);
9
10 for (let j = 0; j < i; j++) {
11 if (arr[i] % arr[j] === 0) {
12 const right = arr[i] / arr[j];
13 if (dp.has(right)) {
14 dp.set(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(right)) % mod);
15 }
16 }
17 }
18
19 result = (result + dp.get(arr[i])) % mod;
20 }
21
22 return result;
23}
24
25// Example usage:
26const arr = [2, 4, 5, 10];
27console.log(numFactoredBinaryTrees(arr));
28In this JavaScript solution, we utilize a map to capture the dynamic programming progress, leveraging key-value pairs for accounting numbers of trees each potential root supports. Sorting allows us to systematically and efficiently determine multiplicative factor pairs. This helps add precise counts for each element as calculations proceed, with a summed result returned modulo 10^9 + 7.