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.
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.
The function first sorts the array to ensure that for every element we can look back and find previous elements that might form factors. We then use dynamic programming to keep track of the number of trees that can be formed with each element as the root. A nested loop considers each possible pair to check if their product matches the current element and updates the possible combinations using previously computed values. The result is computed modulo 10^9 + 7.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with HashMap | 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. |
| Default Approach | — |
| 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. |
Binary Trees With Factors | Easy Intuition | Dry Run | GOOGLE | Leetcode - 823 • codestorywithMIK • 8,436 views views
Watch 9 more video solutions →Practice Binary Trees With Factors with our built-in code editor and test cases.
Practice on FleetCode