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 <iostream>
2#include <vector>
3#include <algorithm>
4#include <unordered_map>
5using namespace std;
6
7#define MOD 1000000007
8
9class Solution {
10public:
11 int numFactoredBinaryTrees(vector<int>& arr) {
12 sort(arr.begin(), arr.end());
13 unordered_map<int, long> dp;
14 long res = 0;
15
16 for (int i = 0; i < arr.size(); i++) {
17 dp[arr[i]] = 1;
18 for (int j = 0; j < i; j++) {
19 if (arr[i] % arr[j] == 0) {
20 int rhs = arr[i] / arr[j];
21 if (dp.find(rhs) != dp.end()) {
22 dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[rhs]) % MOD;
23 }
24 }
25 }
26 res = (res + dp[arr[i]]) % MOD;
27 }
28
29 return res;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> arr = {2, 4, 5, 10};
36 cout << sol.numFactoredBinaryTrees(arr) << endl;
37 return 0;
38}In this C++ implementation, we first sort the input array to assess each element in increasing order of size. An unordered map is employed as the dynamic programming table to track the number of ways to form trees with each node as root. We iterate through each possible pair for every element to see if both factors exist within already evaluated elements. If so, we compute the resultant count of additional trees and incrementally build towards the final result, returning it modulo 10^9 + 7.