Scale Engineer

Binary Trees With Factors

Med
#0777Time: Exponential, likely O(N^N) or worse. The number of recursive calls grows very rapidly without memoization, as each call can spawn `O(N)` new pairs of recursive calls.Space: O(N), where N is the length of `arr`. This is for the recursion stack depth in the worst case (e.g., for an input like `[2, 4, 8, 16, ...]`).
Patterns
Dynamic Programming
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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:

[2], [4], [4, 2, 2]

Example 2:

[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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a plain recursive function to count the number of trees for each number in the input array. For each number x, we consider it as a root. The number of trees with root x is 1 (for the leaf node) plus the sum of products of the number of trees for its possible children. We find pairs of factors (y, z) of x that are also present in the input array. The number of ways to form a tree with x as the root and y, z as children is the product of the number of ways to form trees with root y and root z. This method does not use memoization, leading to re-computation of results for the same subproblems.

Algorithm

  1. Create a HashSet from the input arr for O(1) average time lookups.
  2. Initialize totalTrees = 0.
  3. For each num in arr: a. Add the result of a recursive function countTrees(num) to totalTrees (modulo 10^9 + 7).
  4. Return totalTrees.

countTrees(root) function:

  1. Initialize count = 1 (for the leaf node).
  2. For each factor1 in arr: a. If root is divisible by factor1: i. Let factor2 = root / factor1. ii. If factor2 is in the HashSet: - Recursively call countTrees(factor1) and countTrees(factor2). - Add the product of their results to count (modulo 10^9 + 7).
  3. Return count.

Walkthrough

We define a recursive function, say countTrees(root), which calculates the number of possible binary trees with the given root value. To make checking for the existence of factors efficient, we first put all elements of arr into a HashSet.

The main function iterates through each number in arr and calls countTrees for it, summing up the results modulo 10^9 + 7.

Inside countTrees(root):

  1. Initialize a counter count to 1, representing the tree with only the root node.
  2. Iterate through each number factor1 in the input array arr.
  3. If root is divisible by factor1, calculate factor2 = root / factor1.
  4. Check if factor2 also exists in the HashSet of array elements.
  5. If it exists, it means we found a valid pair of children. We recursively call countTrees(factor1) and countTrees(factor2) and add their product to our count.
  6. Return the final count.

This approach is very slow because it recomputes the results for the same subproblems multiple times. For example, countTrees(2) would be calculated repeatedly whenever 2 appears as a factor in the recursion tree.

// Note: This solution is for demonstration and will cause Time Limit Exceeded.import java.util.HashSet;import java.util.Set; class Solution {    private Set<Integer> numSet;    private int[] arr;    private long MOD = 1_000_000_007;     public int numFactoredBinaryTrees(int[] arr) {        this.arr = arr;        this.numSet = new HashSet<>();        for (int x : arr) {            numSet.add(x);        }         long totalTrees = 0;        for (int num : arr) {            totalTrees = (totalTrees + countTrees(num)) % MOD;        }        return (int) totalTrees;    }     private long countTrees(int root) {        long count = 1; // The tree with just the root        for (int factor1 : arr) {            if (root > factor1 && root % factor1 == 0) {                int factor2 = root / factor1;                if (numSet.contains(factor2)) {                    long ways1 = countTrees(factor1);                    long ways2 = countTrees(factor2);                    count = (count + (ways1 * ways2)) % MOD;                }            }        }        return count;    }}

Complexity

Time

Exponential, likely O(N^N) or worse. The number of recursive calls grows very rapidly without memoization, as each call can spawn `O(N)` new pairs of recursive calls.

Space

O(N), where N is the length of `arr`. This is for the recursion stack depth in the worst case (e.g., for an input like `[2, 4, 8, 16, ...]`).

Trade-offs

Pros

  • Simple to conceptualize as it directly translates the problem's recursive structure.

Cons

  • Extremely inefficient due to massive redundant computations.

  • Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.

  • The recursion depth can be large, potentially leading to a StackOverflowError.

Solutions

class Solution { public int numFactoredBinaryTrees ( int [] arr ) { final int mod = ( int ) 1 e9 + 7 ; Arrays . sort ( arr ); int n = arr . length ; long [] f = new long [ n ]; Arrays . fill ( f , 1 ); Map < Integer , Integer > idx = new HashMap <>( n ); for ( int i = 0 ; i < n ; ++ i ) { idx . put ( arr [ i ], i ); } for ( int i = 0 ; i < n ; ++ i ) { int a = arr [ i ]; for ( int j = 0 ; j < i ; ++ j ) { int b = arr [ j ]; if ( a % b == 0 ) { int c = a / b ; if ( idx . containsKey ( c )) { int k = idx . get ( c ); f [ i ] = ( f [ i ] + f [ j ] * f [ k ]) % mod ; } } } } long ans = 0 ; for ( long v : f ) { ans = ( ans + v ) % mod ; } return ( int ) ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem