823 - Binary Trees With Factors

Difficulty: Medium | Pattern: Dynamic Programming + HashMap | Company tags: Amazon, Google

Problem Statement

Given an array of unique integers arr where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [2,4]
Output: 3
Explanation: [2], [4], [4,2,2]

Example 2:

Input: arr = [2,4,5,10]
Output: 7  ([2],[4],[5],[10],[4,2,2],[10,2,5],[10,5,2])

Approach: DP — O(n² / something), O(n)

Key insight: Sort arr. dp[x] = number of trees with root x. For each x, try all pairs of factors (a, b) where a * b == x and both a, b are in arr.

dp[x] = 1 + sum(dp[a] * dp[b]) for all a, b in arr where a*b==x

The +1 accounts for the single-node tree.

Algorithm Flow

def numFactoredBinaryTrees(arr: list[int]) -> int:
    MOD = 10**9 + 7
    arr.sort()
    dp = {}
    
    for i, x in enumerate(arr):
        dp[x] = 1  # single node
        for j in range(i):
            a = arr[j]
            if x % a == 0:
                b = x // a
                if b in dp:
                    dp[x] += dp[a] * dp[b]
        dp[x] %= MOD
    
    return sum(dp.values()) % MOD

Dry Run

arr = [2,4,5,10]

x	factors (a,b)	dp[x]
2	none	1
4	(2,2) → dp[2]*dp[2]=1	1+1=2
5	none	1
10	(2,5)→11, (5,2)→11	1+1+1=3

Sum: 1+2+1+3 = 7 ✓

Complexity

• Time: O(n²) — for each of n elements, try O(n) factor pairs
• Space: O(n)

Key Terms

Term	Definition
Dynamic Programming (DP)	Building the answer for a value from previously-computed answers for smaller values.
dp[x]	Number of distinct binary trees that can be rooted at value x.
Factor pair	Two values a, b from arr such that a * b == x.
Modulo arithmetic	Taking results mod 10^9 + 7 to avoid integer overflow on large counts.
Sorting invariant	Processing arr in ascending order guarantees both factors of x are already computed when x is reached.

FAQ

Q: Why must arr be sorted before running the DP? A: Because a factor pair (a, b) of x always has a, b < x (since both are > 1), sorting guarantees dp[a] and dp[b] are already finalized before we compute dp[x].

Q: Can two different factor pairs both contribute to the same x? A: Yes — e.g., for x = 10 with factors 2 and 5, both (2,5) and (5,2) are counted separately because the left/right child assignment produces distinct trees.

Q: What if arr has duplicate root values, like 4 appearing twice in different subtrees? A: The array itself has unique integers (per constraints), but the same value can still be reused as a leaf or internal node arbitrarily many times when building trees, which is why dp[x] doesn't need multiplicity tracking.

Q: How would you extend this to N-ary trees where a node's value is the product of k children? A: You would need to enumerate all ways to partition x into k factors from arr, which is significantly more expensive — typically requires memoized recursion over combinations rather than simple pairwise DP.

Q: What's the follow-up interviewers usually ask? A: "Can you avoid recomputation if arr changes incrementally (add/remove one element)?" — the answer involves recomputing only dp entries for multiples of the changed value.

Quick Revision

• Pattern: DP over sorted values + hashmap lookup for factor pairs.
• dp[x] = 1 (single node) + sum of dp[a] * dp[b] for every factor pair (a, b) of x present in arr.
• Sort arr first so smaller factors are always resolved before larger products.
• Use a hashmap (dp dict) keyed by value for O(1) factor lookups.
• Iterate only over j < i to enforce a <= x and avoid double work.
• Final answer is the sum of all dp[x] values, taken mod 10^9 + 7.
• Time complexity O(n²) since each element checks up to n potential factors.
• Space complexity O(n) for the dp hashmap.
• Edge case: if no element divides another, every dp[x] = 1 and the answer is just n.

Related Problems

• 1048 - Longest String Chain — same "sort then DP building larger from smaller via a hashmap-checked relation" pattern.
• 132 - Palindrome Partitioning II (LeetCode) — interval/value DP with precomputed sub-results, same style of composing an answer from smaller validated pieces.
• 96 - Unique Binary Search Trees (LeetCode) — counts distinct binary trees via DP, directly analogous combinatorial counting problem.