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.
1#include <stdio.h>
2#include <stdlib.h>
3#define MOD 1000000007
4
5int cmpfunc(const void *a, const void *b) {
6 return *(int*)a - *(int*)b;
7}
8
9int numFactoredBinaryTrees(int* arr, int arrSize) {
10 qsort(arr, arrSize, sizeof(int), cmpfunc);
11 long *dp = (long *)malloc(sizeof(long) * arrSize);
12 for (int i = 0; i < arrSize; i++)
13 dp[i] = 1;
14
15 long result = 0;
16 for (int i = 0; i < arrSize; i++) {
17 for (int j = 0; j < i; j++) {
18 if (arr[i] % arr[j] == 0) {
19 int right = arr[i] / arr[j];
20 for (int k = 0; k < arrSize; k++)
21 if (arr[k] == right)
22 dp[i] = (dp[i] + dp[j] * dp[k]) % MOD;
23 }
24 }
25 result = (result + dp[i]) % MOD;
26 }
27 free(dp);
28 return result;
29}
30
31int main() {
32 int arr[] = {2, 4, 5, 10};
33 int arrSize = sizeof(arr) / sizeof(arr[0]);
34 int result = numFactoredBinaryTrees(arr, arrSize);
35 printf("%d\n", result);
36 return 0;
37}The function first sorts the array to ensure that for every element we can look back and find previous elements that might form factors. We then use dynamic programming to keep track of the number of trees that can be formed with each element as the root. A nested loop considers each possible pair to check if their product matches the current element and updates the possible combinations using previously computed values. The result is computed modulo 10^9 + 7.