Skip to main content
Talentd

Binary Trees With Factors - Solution & Explanation

MediumArrayHash TableDynamic ProgrammingSorting12 min readAsked at: Amazon, Google
Practice this problem

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 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 <= 1000
  • 2 <= arr[i] <= 109
  • All the values of arr are unique.

Approach Overview

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 1: Dynamic Programming with HashMap

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Factor EnumerationExponential (~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.

Video Solution

Binary Trees With Factors | Easy Intuition | Dry Run | GOOGLE | Leetcode - 823 • codestorywithMIK • 9,033 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Trees With Factors easy or hard?
Binary Trees With Factors is generally considered a medium difficulty problem. The challenge comes from recognizing the factor-pair relationship and converting the recursive idea into an efficient O(n^2) dynamic programming solution.
How to solve Binary Trees With Factors in O(n^2)?
First sort the array so smaller numbers are processed earlier. Maintain a hash map dp[value] representing the number of trees with that value as root. For each element x, iterate through previous elements a; if x % a == 0 and b = x/a exists in the map, update dp[x] += dp[a] * dp[b]. This dynamic programming build-up gives O(n^2) time complexity.
What is the best approach for Binary Trees With Factors?
The optimal approach uses dynamic programming with a hash map after sorting the array. For each value x, iterate over smaller values a and check if a valid factor pair (a, x/a) exists. The number of trees rooted at x equals the sum of dp[a] * dp[b] for all factor pairs. This runs in O(n^2) time and O(n) space.
Is Binary Trees With Factors asked at Google/Amazon/Meta?
Binary Trees With Factors appears in interview prep lists for companies such as Amazon and Google because it combines dynamic programming, factor decomposition, and hash map optimization. It tests the ability to build solutions incrementally using sorted input and memoization.
What data structure is used in Binary Trees With Factors?
The main data structure is a hash map that stores the number of trees rooted at each value. Sorting the array enables a bottom-up dynamic programming process where smaller factors are computed before larger products.
What is the time complexity of Binary Trees With Factors?
The optimized solution runs in O(n^2) time. Each element is treated as a root, and the algorithm checks all smaller elements as potential factors. Hash map lookups keep factor existence checks constant time, while the DP table stores subtree counts.
Binary Trees With Factors Python or Java solution approach?
Python and Java implementations both follow the same pattern: sort the array, maintain a map from value to DP count, iterate through factor pairs, and accumulate results modulo 1e9+7. The logic stays identical across Python, Java, C++, C#, and JavaScript.

Ready to solve this problem?

Practice Binary Trees With Factors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays