Problem Breakdown
We are given an array arr containing unique integers greater than 1. We need to construct binary trees such that every non-leaf node’s value is the product of its children’s values. The goal is to count all possible valid binary trees using elements from arr.
Key constraints:
- Node Values: Must be present in
arr(can reuse numbers). - Structure: Root = Left Child × Right Child. Single nodes are always valid trees.
- Output: Total count modulo .
Intuition
A brute-force recursive approach is inefficient due to overlapping subproblems and the exponential growth of tree structures. We can optimize using Dynamic Programming (DP).
State Definition: Let dp[v] be the number of valid binary trees rooted with value v.
- Base Case: Every element in
arrforms at least one single-node tree, so initiallydp[x] = 1for all . - Transition: For a root
root, if it has childrenleftandrightsuch thatleft * right == root, then the number of ways to form this specific structure isdp[left] * dp[right]. Since binary trees distinguish left/right, both permutations and count as distinct structures unless . - Order: To ensure we have computed DP values for all potential children before computing the parent, we must process numbers in increasing order. This guarantees that when calculating
dp[root], any valid factor (child) has already been processed.
Approach
- Sort the input array
arrto handle dependencies from smallest factors to largest roots. - Initialize a hash map (
dp) where each key is an element ofarrand value starts at 1 (representing the single-node tree). - Iterate through each number in the sorted array as a potential root node:
- For every previous number in the array, check if it divides the current root evenly.
- If divisible (
root % prev == 0), calculateother = root // prev. - Check if
otherexists in our DP map (which implies it is a valid element fromarr). - Add
dp[prev] * dp[other]to the current count forroot, applying modulo at each step.
- Sum all values in the
dpmap and return the result modulo .
Complexity Analysis
- Time: Sorting takes . The nested loop iterates through pairs of elements, resulting in operations. Given , this is approximately iterations, which fits well within time limits for Python ( ops/sec).
- Space: We store DP counts and existence checks in a hash map. Space Complexity: .
Solution
class Solution:
def numFactoredBinaryTrees(self, arr):
MOD = 10**9 + 7
# Sort array to process smaller factors first (bottom-up DP)
arr.sort()
# Map value -> count of trees rooted at that value.
# Initialize all with 1 because every number can be a single-node tree itself.
dp = {x: 1 for x in arr}
# Iterate through each element as the potential root node
for i, num in enumerate(arr):
# Check against all previous elements to find valid left children
for j in range(i):
prev = arr[j]
# If 'prev' divides 'num', check if the other factor exists
if num % prev == 0:
other = num // prev
# Since we sorted, any valid child must be smaller than root.
# We only need to ensure 'other' is actually in our input set (and thus has a DP count).
if other in dp:
# Add combinations of trees from left and right children
# Note: The loop structure handles distinct pairs naturally by checking every prev as potential Left Child.
# If we find valid pair (prev, other), it contributes to 'num'.
# Since binary tree order matters (Left vs Right):
# When j points to a specific factor A and B is the complement:
# We add dp[A] * dp[B].
# Later in this same outer loop iteration? No.
# If we find valid pair (A, B) where both exist in arr:
# Case 1: A < B. When j points to index of A, other=B exists -> add dp[A]*dp[B].
# Case 2: B > A is covered by the fact that if B also divides num and appears earlier (B < num),
# then when j points to B, other=A exists -> add dp[B]*dp[A].
count = (dp[prev] * dp[other]) % MOD
dp[num] = (dp[num] + count) % MOD
return sum(dp.values()) % MOD
Edge Cases Handled
- Single Element Array: The loop runs once, inner loop doesn’t run. Returns 1 (correct).
- No Factors Found: If a number is prime relative to the array elements provided, it remains at base count of 1. Summation handles this correctly.
- Perfect Square Roots: E.g.,
arr = [2, 4]. For root 4: factor pair (2, 2). Loop checksprev=2, calculatesother=2. Since2is in map, addsdp[2]*dp[2]. This counts the single structural tree[4; 2, 2]once. - Large Values: Modulo arithmetic applied at every addition step to prevent integer overflow and meet return requirement (though Python handles large ints automatically).