Binary Trees With Factors solution and explanation
Google
9 more videos on this problem
Binary Trees With Factors | Easy Intuition | Dry Run | GOOGLE | Leetcode - 823codestorywithMIK · 32:32 · 9K views
Leetcode 823. Binary Trees With Factors #Binary Tree #Leetcode #823Code with Alisha · 24:37 · 7K views
Binary Trees With Factors | Leetcode 823Coding Decoded · 23:50 · 3K views
Binary Trees With Factors | Live Coding | 823 LeetCode | LeetCode Explore | Day 28CodeWithSunny · 10:00 · 3K views
LeetCode 823. Binary Trees With FactorsHappy Coding · 16:08 · 1K views
Leetcode - Binary Trees With Factors (Python)Timothy H Chang · 6:20 · 1K views
823. Binary Trees with Factors - Daily LeetCodeTechTalk · 7:41 · 1K views
Daily Leetcode #861: Aug 09, 2022 - 823. Binary Trees With FactorsProgramming Live with Larry · 10:42 · 608 views
✅ Binary Trees With Factors✅ How to answer in Interview ✅ Dynamic Programming ✅ Leetcode 823Leet Logics · 9:12 · 570 views
Binary Trees With Factors 🔥 | Live Coding a LeetCode 823 Problem with Dynamic ProgrammingvanAmsen · 7:47 · 565 views
The problem
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] <= 109- All the values of
arrare 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.
from collections import defaultdict
def numFactoredBinaryTrees(arr):
arr.sort()
mod = 10**9 + 7
dp = defaultdict(int)
res = 0
for i, x in enumerate(arr):
dp[x] = 1
for j in range(i):
if x % arr[j] == 0: # arr[j] is one of the children
right = x // arr[j]
if right in dp:
dp[x] += dp[arr[j]] * dp[right]
dp[x] %= mod
res += dp[x]
res %= mod
return res
# Example usage:
arr = [2, 4, 5, 10]
print(numFactoredBinaryTrees(arr))import java.util.*;
public class Solution {
public int numFactoredBinaryTrees(int[] arr) {
Arrays.sort(arr);
long mod = 1000000007;
Map<Integer, Long> dp = new HashMap<>();
long result = 0;
for (int i = 0; i < arr.length; i++) {
dp.put(arr[i], 1L);
for (int j = 0; j < i; j++) {
if (arr[i] % arr[j] == 0) { // arr[j] can be left child
int right = arr[i] / arr[j];
if (dp.containsKey(right)) {
dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(right)) % mod);
}
}
}
result = (result + dp.get(arr[i])) % mod;
}
return (int) result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {2, 4, 5, 10};
System.out.println(sol.numFactoredBinaryTrees(arr));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define MOD 1000000007
class Solution {
public:
int numFactoredBinaryTrees(vector<int>& arr) {
sort(arr.begin(), arr.end());
unordered_map<int, long> dp;
long res = 0;
for (int i = 0; i < arr.size(); i++) {
dp[arr[i]] = 1;
for (int j = 0; j < i; j++) {
if (arr[i] % arr[j] == 0) {
int rhs = arr[i] / arr[j];
if (dp.find(rhs) != dp.end()) {
dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[rhs]) % MOD;
}
}
}
res = (res + dp[arr[i]]) % MOD;
}
return res;
}
};
int main() {
Solution sol;
vector<int> arr = {2, 4, 5, 10};
cout << sol.numFactoredBinaryTrees(arr) << endl;
return 0;
}function numFactoredBinaryTrees(arr) {
arr.sort((a, b) => a - b);
const mod = 1000000007;
const dp = new Map();
let result = 0;
for (let i = 0; i < arr.length; i++) {
dp.set(arr[i], 1);
for (let j = 0; j < i; j++) {
if (arr[i] % arr[j] === 0) {
const right = arr[i] / arr[j];
if (dp.has(right)) {
dp.set(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(right)) % mod);
}
}
}
result = (result + dp.get(arr[i])) % mod;
}
return result;
}
// Example usage:
const arr = [2, 4, 5, 10];
console.log(numFactoredBinaryTrees(arr));#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int cmpfunc(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int numFactoredBinaryTrees(int* arr, int arrSize) {
qsort(arr, arrSize, sizeof(int), cmpfunc);
long *dp = (long *)malloc(sizeof(long) * arrSize);
for (int i = 0; i < arrSize; i++)
dp[i] = 1;
long result = 0;
for (int i = 0; i < arrSize; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] % arr[j] == 0) {
int right = arr[i] / arr[j];
for (int k = 0; k < arrSize; k++)
if (arr[k] == right)
dp[i] = (dp[i] + dp[j] * dp[k]) % MOD;
}
}
result = (result + dp[i]) % MOD;
}
free(dp);
return result;
}
int main() {
int arr[] = {2, 4, 5, 10};
int arrSize = sizeof(arr) / sizeof(arr[0]);
int result = numFactoredBinaryTrees(arr, arrSize);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int NumFactoredBinaryTrees(int[] arr) {
Array.Sort(arr);
long mod = 1000000007;
var dp = new Dictionary<int, long>();
long result = 0;
foreach (int num in arr) {
dp[num] = 1;
foreach (var key in dp.Keys) {
if (num % key == 0) {
int right = num / key;
if (dp.ContainsKey(right)) {
dp[num] = (dp[num] + dp[key] * dp[right]) % mod;
}
}
}
result = (result + dp[num]) % mod;
}
return (int)result;
}
public static void Main() {
var solution = new Solution();
int[] arr = {2, 4, 5, 10};
Console.WriteLine(solution.NumFactoredBinaryTrees(arr));
}
}This Python solution involves sorting the array and employing a dictionary (defaultdict from collections) to store the number of ways each element can be the root of binary trees. For each element, it examines all preceding elements to find valid multiplication pairs using remainder checks. When found, it increments the count for the current element by all factor combinations stored previously.
Time Complexity: O(n^2), due to the nested loop structure increasing in step with elements.
Space Complexity: O(n), since storage for dp requires space proportionate to the input's unique elements.
Approach 2: Default Approach
function numFactoredBinaryTrees(arr: number[]): number {
const mod = 10 ** 9 + 7;
arr.sort((a, b) => a - b);
const idx: Map<number, number> = new Map();
const n = arr.length;
for (let i = 0; i < n; ++i) {
idx.set(arr[i], i);
}
const f: number[] = new Array(n).fill(1);
for (let i = 0; i < n; ++i) {
const a = arr[i];
for (let j = 0; j < i; ++j) {
const b = arr[j];
if (a % b === 0) {
const c = a / b;
if (idx.has(c)) {
const k = idx.get(c)!;
f[i] = (f[i] + f[j] * f[k]) % mod;
}
}
}
}
return f.reduce((a, b) => a + b) % mod;
}func numFactoredBinaryTrees(arr []int) int {
const mod int = 1e9 + 7
sort.Ints(arr)
f := make([]int, len(arr))
idx := map[int]int{}
for i, v := range arr {
f[i] = 1
idx[v] = i
}
for i, a := range arr {
for j := 0; j < i; j++ {
b := arr[j]
if c := a / b; a%b == 0 {
if k, ok := idx[c]; ok {
f[i] = (f[i] + f[j]*f[k]) % mod
}
}
}
}
ans := 0
for _, v := range f {
ans = (ans + v) % mod
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with HashMap | Time Complexity: O(n^2), due to the nested loop structure increasing in step with elements. Space Complexity: O(n), since storage for dp requires space proportionate to the input's unique elements. |
| Default Approach | – |
Complexity analysis
| 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. |
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.