Watch 10 video solutions for Binary Trees With Factors, a medium level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by codestorywithMIK has 8,436 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 109 + 7.
Example 1:
Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
Example 2:
Input: arr = [2,4,5,10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
Constraints:
1 <= arr.length <= 10002 <= arr[i] <= 109arr are unique.Problem Overview: You are given an array of unique integers. Build binary trees where every non‑leaf node equals the product of its left and right child. Each value in the array can be used multiple times. The goal is to count how many different binary trees can be formed.
Approach 1: Brute Force Factor Enumeration (Exponential)
For each value x in the array, try every pair of numbers (a, b) where a * b = x. Recursively count the number of trees rooted at a and b. The total trees for x become the product of possibilities from both subtrees. Without caching, the recursion repeatedly recomputes the same subtree counts, causing exponential growth in time. Time complexity grows roughly O(2^n) in the worst case with O(n) recursion space. This approach helps understand the factor relationship but quickly becomes impractical.
Approach 2: Dynamic Programming with HashMap (O(n2) time, O(n) space)
Sort the array first so smaller factors appear before larger values. Use a hash map where dp[x] stores the number of binary trees rooted at value x. Iterate through the sorted array and treat each number as a root. For every earlier element a, check if x % a == 0. If the complementary factor b = x / a exists in the map, combine the counts: dp[x] += dp[a] * dp[b]. This works because all smaller factor trees are already computed. Sorting plus constant-time hash lookups keeps the total complexity at O(n^2) time with O(n) space.
The key insight is that every valid tree is defined by factor pairs of its root value. Once the array is sorted, dynamic programming builds larger trees from previously computed smaller ones. The hash map guarantees constant-time existence checks for factors.
Recommended for interviews: The dynamic programming approach with sorting and a hash map. Interviewers expect you to recognize that each root value can be decomposed into factor pairs and that previously computed results can be reused. Brute force demonstrates the relationship between products and subtrees, but the DP + hash lookup solution shows algorithmic maturity.
This problem combines ideas from array traversal, fast lookups using a hash table, and bottom‑up dynamic programming after sorting the values.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Factor Enumeration | Exponential (~O(2^n)) | O(n) | Useful for understanding the recursive structure of factor-based trees. |
| Dynamic Programming + HashMap (Sorted Array) | O(n^2) | O(n) | Best general solution. Efficient for arrays up to the problem constraints. |