Binary Trees With Factors — Solution in Python, Java & C++
Binary Trees With Factors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Binary Trees With Factors is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Dynamic Programming, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
arr holds distinct integers, each greater than 1. Build binary trees whose node values are taken from arr — any value may be used any number of times — subject to one rule: every non-leaf node has exactly two children and its value equals the product of its children's values.
Count how many such trees exist. A single node is a tree; two trees are different if their shapes or any node values differ (so swapping the two children of a node gives a different tree when the children differ).
Return the count modulo 10^9 + 7.
Example 1
Input: arr = [2,4]
Output: 3
Explanation: `[2]`, `[4]` and `4` with children `2, 2`.
Example 2
Input: arr = [2,4,5,10]
Output: 7
Explanation: Four single nodes, `4 → (2,2)`, `10 → (2,5)` and `10 → (5,2)`.
Example 3
Input: arr = [3,7,11]
Output: 3
Constraints
1 <= arr.length <= 10002 <= arr[i] <= 10^9All values of arr are distinct
Hints for Binary Trees With Factors
Hint 1
The root's value is the product of its children's values, so both children are smaller than the root.
Hint 2
Process values in increasing order and count the trees rooted at each value.
Hint 3
trees(v) = 1 + Σ trees(a) · trees(v / a) over every
ainarrthat dividesvwithv / aalso inarr.
How to solve Binary Trees With Factors
A tree rooted at v is either the single node v or a choice of left child value a and right child value v / a (both in arr) with any tree under each. Children are strictly smaller, so counting in increasing order of value works.
Approach
- Sort
arrand index each value with a hash map. - For each value
vin increasing order, startways[v] = 1(the leaf). - For every smaller
athat dividesvwhereb = v / ais in the map, addways[a] · ways[b](mod10^9 + 7). - Return the sum of
waysover all values, modulo10^9 + 7.
Why it works
Every tree with root v and at least two nodes is determined uniquely by the ordered pair (left subtree, right subtree), whose roots multiply to v. Summing over ordered divisor pairs (a, v/a) counts each such pair of subtrees exactly once — (a, b) and (b, a) are distinct when a ≠ b, matching the rule that mirrored trees differ.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Products of two residues reach about 10^18: multiply in 64-bit (and in JavaScript split the multiplication, since doubles are exact only to 2^53).
- The pair
(a, a)withv = a²must be counted once, not twice. - Values reach 10^9, so never compute
a · bin 32-bit to test for a factor — testv % a == 0instead.
Reference solution
Python
from typing import List
def numFactoredBinaryTrees(arr: List[int]) -> int:
MOD = 10**9 + 7
a = sorted(arr)
pos = {v: i for i, v in enumerate(a)}
ways = [1] * len(a)
for i in range(len(a)):
for j in range(i):
if a[i] % a[j] == 0:
q = a[i] // a[j]
if q in pos:
ways[i] = (ways[i] + ways[j] * ways[pos[q]]) % MOD
return sum(ways) % MODJava
public static int numFactoredBinaryTrees(int[] arr) {
final long MOD = 1000000007L;
int[] a = arr.clone();
Arrays.sort(a);
int n = a.length;
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < n; i++) pos.put(a[i], i);
long[] ways = new long[n];
long total = 0;
for (int i = 0; i < n; i++) {
ways[i] = 1;
for (int j = 0; j < i; j++) {
if (a[i] % a[j] == 0) {
Integer q = pos.get(a[i] / a[j]);
if (q != null) ways[i] = (ways[i] + ways[j] * ways[q]) % MOD;
}
}
total = (total + ways[i]) % MOD;
}
return (int) total;
}C++
int numFactoredBinaryTrees(vector<int>& arr) {
const long long MOD = 1000000007LL;
vector<int> a(arr.begin(), arr.end());
sort(a.begin(), a.end());
int n = a.size();
unordered_map<int, int> pos;
for (int i = 0; i < n; i++) pos[a[i]] = i;
vector<long long> ways(n, 1);
long long total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[i] % a[j] == 0) {
auto it = pos.find(a[i] / a[j]);
if (it != pos.end()) ways[i] = (ways[i] + ways[j] * ways[it->second]) % MOD;
}
}
total = (total + ways[i]) % MOD;
}
return (int) total;
}JavaScript
var numFactoredBinaryTrees = function(arr) {
var MOD = 1000000007;
var mulmod = function(x, y) {
return ((x * (y >>> 16)) % MOD * 65536 + x * (y & 65535)) % MOD;
};
var a = arr.slice().sort(function(x, y) { return x - y; });
var pos = new Map();
for (var i = 0; i < a.length; i++) pos.set(a[i], i);
var ways = new Array(a.length).fill(1);
var total = 0;
for (i = 0; i < a.length; i++) {
for (var j = 0; j < i; j++) {
if (a[i] % a[j] === 0) {
var q = a[i] / a[j];
if (pos.has(q)) ways[i] = (ways[i] + mulmod(ways[j], ways[pos.get(q)])) % MOD;
}
}
total = (total + ways[i]) % MOD;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets