Binary Trees With Factors

Medium
1476.

Binary Trees With Factors

Binary Trees With Factors is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.

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 <= 1000
  • 2 <= arr[i] <= 10^9
  • All values of arr are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var numFactoredBinaryTrees = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 2 <= arr[i] <= 10^9
  • All values of arr are distinct

Hints for Binary Trees With Factors

  1. Hint 1

    The root's value is the product of its children's values, so both children are smaller than the root.

  2. Hint 2

    Process values in increasing order and count the trees rooted at each value.

  3. Hint 3

    trees(v) = 1 + Σ trees(a) · trees(v / a) over every a in arr that divides v with v / a also in arr.

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

  1. Sort arr and index each value with a hash map.
  2. For each value v in increasing order, start ways[v] = 1 (the leaf).
  3. For every smaller a that divides v where b = v / a is in the map, add ways[a] · ways[b] (mod 10^9 + 7).
  4. Return the sum of ways over all values, modulo 10^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) with v = a² must be counted once, not twice.
  • Values reach 10^9, so never compute a · b in 32-bit to test for a factor — test v % a == 0 instead.

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) % MOD

Java

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