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.
1from collections import defaultdict
2
3def numFactoredBinaryTrees(arr):
4 arr.sort()
5 mod = 10**9 + 7
6 dp = defaultdict(int)
7 res = 0
8
9 for i, x in enumerate(arr):
10 dp[x] = 1
11 for j in range(i):
12 if x % arr[j] == 0: # arr[j] is one of the children
13 right = x // arr[j]
14 if right in dp:
15 dp[x] += dp[arr[j]] * dp[right]
16 dp[x] %= mod
17 res += dp[x]
18 res %= mod
19 return res
20
21# Example usage:
22arr = [2, 4, 5, 10]
23print(numFactoredBinaryTrees(arr))This Python solution involves sorting the array and employing a dictionary (defaultdict from collections) to store the number of ways each element can be the root of binary trees. For each element, it examines all preceding elements to find valid multiplication pairs using remainder checks. When found, it increments the count for the current element by all factor combinations stored previously.