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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int NumFactoredBinaryTrees(int[] arr) {
6 Array.Sort(arr);
7 long mod = 1000000007;
8 var dp = new Dictionary<int, long>();
9 long result = 0;
10
11 foreach (int num in arr) {
12 dp[num] = 1;
13
14 foreach (var key in dp.Keys) {
15 if (num % key == 0) {
16 int right = num / key;
17 if (dp.ContainsKey(right)) {
18 dp[num] = (dp[num] + dp[key] * dp[right]) % mod;
19 }
20 }
21 }
22
23 result = (result + dp[num]) % mod;
24 }
25
26 return (int)result;
27 }
28
29 public static void Main() {
30 var solution = new Solution();
31 int[] arr = {2, 4, 5, 10};
32 Console.WriteLine(solution.NumFactoredBinaryTrees(arr));
33 }
34}
35This C# solution uses a sorted array strategy and a dictionary to keep track of the number of binary trees each integer can root. Each element is assessed against previous ones to identify valid factor pairs. The inner loop computes possible trees by referring to entries already processed, helping to accumulate a total count submitted as the final answer modulo 10^9 + 7.