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.
1import java.util.*;
2
3public class Solution {
4 public int numFactoredBinaryTrees(int[] arr) {
5 Arrays.sort(arr);
6 long mod = 1000000007;
7 Map<Integer, Long> dp = new HashMap<>();
8 long result = 0;
9
10 for (int i = 0; i < arr.length; i++) {
11 dp.put(arr[i], 1L);
12 for (int j = 0; j < i; j++) {
13 if (arr[i] % arr[j] == 0) { // arr[j] can be left child
14 int right = arr[i] / arr[j];
15 if (dp.containsKey(right)) {
16 dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(right)) % mod);
17 }
18 }
19 }
20 result = (result + dp.get(arr[i])) % mod;
21 }
22
23 return (int) result;
24 }
25
26 public static void main(String[] args) {
27 Solution sol = new Solution();
28 int[] arr = {2, 4, 5, 10};
29 System.out.println(sol.numFactoredBinaryTrees(arr));
30 }
31}The Java solution utilizes sorting followed by a dynamic programming strategy stored in a HashMap. It counts the number of trees possible for each integer by evaluating previous integers to see if they can be factors, updating the tree count for each new root appropriately. The results increment as each integer is processed, with the total number of trees obtained at the end reduced modulo 10^9 + 7.