Problem Description

You are given an array of unique integers where each integer is strictly greater than 1. Your task is to count how many binary trees can be constructed using these integers as node values, following a specific rule: each non-leaf node's value must equal the product of its two children's values.

The key points of this problem are:

1. Available numbers: You can use any integer from the given array arr as a node value
2. Reusability: Each number can be used multiple times across different nodes in the tree
3. Parent-child relationship: For any non-leaf node with value parent, if its children have values left and right, then parent = left × right
4. Leaf nodes: These can be any value from the array with no multiplication constraint
5. Return value: The total count of valid binary trees modulo 10^9 + 7

For example, if arr = [2, 4], you can create three valid trees:

• A single node with value 2
• A single node with value 4
• A tree with root 4 and two children both having value 2 (since 2 × 2 = 4)

The solution uses dynamic programming where f[i] represents the number of binary trees that can be formed with arr[i] as the root. For each element arr[i], it checks all possible factorizations where arr[i] = arr[j] × arr[k] and accumulates the count by multiplying the number of trees possible with arr[j] as root and arr[k] as root.

Intuition

The key insight is recognizing this as a dynamic programming problem where we build up solutions for larger numbers using solutions for smaller numbers.

Think about it this way: if we want to count trees with a particular value a as the root, we need to consider all possible ways to factor a into two parts that will become its children. For instance, if a = 12 and we have 3 and 4 in our array, then 12 = 3 × 4, so we can make a tree with root 12 and children 3 and 4.

But here's the crucial observation: the number of trees with root 12 depends on how many different trees we can make with 3 as root and how many with 4 as root. If there are x ways to make trees with root 3 and y ways to make trees with root 4, then there are x × y ways to make trees with root 12 having these specific children.

This naturally leads to a bottom-up approach:

1. Start with the smallest numbers - they can only form single-node trees (count = 1)
2. For larger numbers, check all possible factorizations
3. For each valid factorization a = b × c, multiply the counts of trees rooted at b and c

Why sort the array? By processing numbers in ascending order, we ensure that when we're calculating the count for a number a, we've already computed the counts for all its potential factors (which must be smaller than a).

The formula f[i] = sum(f[j] × f[k]) for all valid pairs (j, k) where arr[i] = arr[j] × arr[k] captures this multiplicative counting principle. Each valid factorization contributes independently to the total count, which is why we add them together.

Learn more about Dynamic Programming and Sorting patterns.

Solution Approach

The solution implements a dynamic programming approach with the following steps:

1. Sorting and Indexing

arr.sort()
idx = {v: i for i, v in enumerate(arr)}

First, we sort the array in ascending order. This ensures we process smaller numbers before larger ones. We also create a dictionary idx that maps each value to its index position for O(1) lookup time when checking if a factor exists in our array.

2. Initialize DP Array

f = [1] * n

We initialize a DP array f where f[i] represents the number of binary trees that can be formed with arr[i] as the root. Each element starts with value 1 because every number can form at least one tree (a single node).

3. Core DP Logic

for i, a in enumerate(arr):
    for j in range(i):
        b = arr[j]
        if a % b == 0 and (c := (a // b)) in idx:
            f[i] = (f[i] + f[j] * f[idx[c]]) % mod

For each number a at position i:

• We iterate through all smaller numbers b at positions j < i
• Check if b is a factor of a using a % b == 0
• If yes, calculate the complementary factor c = a // b
• Check if c exists in our array using the idx dictionary
• If both factors exist, we can form trees with a as root, b as left child, and c as right child
• The number of such trees is f[j] × f[idx[c]] (multiplication principle)
• Add this to our running total for f[i]

4. Modular Arithmetic Throughout the computation, we apply modulo 10^9 + 7 to prevent integer overflow, as the counts can become very large.

5. Final Result

return sum(f) % mod

The total number of binary trees is the sum of all f[i] values, as each element can serve as the root of different trees.

Time Complexity: O(n²) where n is the length of the array, as we have nested loops over the array elements.

Space Complexity: O(n) for the DP array and the index dictionary.

Example Walkthrough

Let's walk through the solution with arr = [2, 4, 8].

Step 1: Sort and Index

• Sorted array: [2, 4, 8] (already sorted)
• Index mapping: {2: 0, 4: 1, 8: 2}
• Initialize DP: f = [1, 1, 1] (each number can form a single-node tree)

Step 2: Process arr[0] = 2

• i = 0, a = 2
• No previous elements to check (j < 0)
• f[0] remains 1 (only single-node tree possible)

Step 3: Process arr[1] = 4

• i = 1, a = 4
• Check j = 0: b = 2
  • Is 2 a factor of 4? Yes (4 % 2 = 0)
  • Complementary factor: c = 4 // 2 = 2
  • Is 2 in our array? Yes (at index 0)
  • Add trees: f[1] = 1 + f[0] × f[0] = 1 + 1 × 1 = 2
• f[1] = 2 (one single-node tree + one tree with root 4 and children 2,2)

Step 4: Process arr[2] = 8

• i = 2, a = 8
• Check j = 0: b = 2
  • Is 2 a factor of 8? Yes
  • Complementary factor: c = 8 // 2 = 4
  • Is 4 in our array? Yes (at index 1)
  • Add trees: f[2] = 1 + f[0] × f[1] = 1 + 1 × 2 = 3
• Check j = 1: b = 4
  • Is 4 a factor of 8? Yes
  • Complementary factor: c = 8 // 4 = 2
  • Is 2 in our array? Yes (at index 0)
  • Add trees: f[2] = 3 + f[1] × f[0] = 3 + 2 × 1 = 5
• f[2] = 5

Step 5: Calculate Total

• Total = f[0] + f[1] + f[2] = 1 + 2 + 5 = 8

The 8 possible trees are:

1. Single node: 2
2. Single node: 4
3. Tree: 4 (root) with children 2, 2
4. Single node: 8
5. Tree: 8 (root) with children 2, 4
6. Tree: 8 (root) with children 4, 2
7. Tree: 8 (root) with children 2, 4 (where 4 itself has children 2, 2)
8. Tree: 8 (root) with children 4, 2 (where 4 itself has children 2, 2)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) where n is the length of the input array.

• Sorting the array takes O(n log n) time
• Creating the index dictionary takes O(n) time
• The nested loops iterate through all pairs where i > j, which gives us approximately n²/2 iterations
• For each iteration, we perform:
  • A modulo operation: O(1)
  • A division operation: O(1)
  • A dictionary lookup to check if c exists: O(1)
  • If the condition is met, another dictionary lookup and arithmetic operations: O(1)
• The final sum operation takes O(n) time

The dominant operation is the nested loops with O(n²) iterations, making the overall time complexity O(n²).

Space Complexity: O(n) where n is the length of the input array.

• The sorted array (in-place sorting in Python creates a new list): O(n)
• The index dictionary idx stores n key-value pairs: O(n)
• The dynamic programming array f stores n values: O(n)
• Temporary variables like i, j, a, b, c: O(1)

The total space complexity is O(n) as we store linear amounts of data relative to the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Duplicate Factor Pairs

A common mistake is counting the same tree structure twice when both factors can serve as either left or right child. For instance, if we have 12 = 3 × 4 and 12 = 4 × 3, these represent different tree structures (3 as left child vs. 4 as left child), and both should be counted.

Why this isn't actually a problem in the given solution: The algorithm naturally handles this by iterating through all possible left children. When j corresponds to value 3, it finds right child 4. When j corresponds to value 4, it finds right child 3. Both configurations are correctly counted.

2. Integer Overflow Issues

The most critical pitfall is forgetting to apply modulo operations at every multiplication step. Without proper modulo application, the intermediate results can overflow even with 64-bit integers.

Incorrect approach:

# WRONG - can cause overflow
dp[i] = dp[i] + dp[j] * dp[right_child_index]
result = sum(dp) % MOD  # Too late to apply modulo

Correct approach:

# RIGHT - apply modulo after each operation
dp[i] = (dp[i] + dp[j] * dp[right_child_index]) % MOD
result = sum(dp) % MOD

3. Not Sorting the Array First

A critical mistake is processing the array without sorting it first. The DP solution relies on the fact that when computing dp[i], all potential children values (which are smaller) have already been processed.

Why sorting is essential:

• Without sorting, you might try to use dp[j] before it's been properly computed
• The algorithm assumes that for any root value, its factors (potential children) have been processed first
• Since factors are always smaller than or equal to their product, sorting ensures correct processing order

Example of the problem: If arr = [4, 2, 8] and we don't sort:

• When processing 4 (index 0), we might miss that 2 (index 1) could be its child
• When processing 8 (index 2), the value for dp[0] (for 4) might not be fully computed

4. Inefficient Factor Checking

Another pitfall is checking if the complementary factor exists using a linear search instead of using a hash map/dictionary for O(1) lookup.

Inefficient approach:

# WRONG - O(n) search for each check
if right_child in arr:  # Linear search
    right_child_index = arr.index(right_child)  # Another linear search

Efficient approach:

# RIGHT - O(1) lookup using dictionary
if right_child in value_to_index:  # O(1) check
    right_child_index = value_to_index[right_child]  # O(1) access

5. Missing Edge Cases

Forgetting that each number can form a single-node tree is a subtle but important oversight. The initialization dp = [1] * n handles this, but it's easy to mistakenly initialize with zeros.

Wrong initialization:

dp = [0] * n  # WRONG - misses single-node trees

Correct initialization:

dp = [1] * n  # RIGHT - each number forms at least one tree (itself)