#823

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Binary Trees With Factors

Given an array of integers, find how many binary trees can be formed such that non-leaf nodes' values are the product of their children.

array hash table dynamic programming sorting

Problem Statement

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1, we need to determine how many binary trees can be formed using these integers. Each number in the array can be used any number of times, and the binary tree must follow the rule that the value of a non-leaf node is the product of its children.

Return the total number of binary trees that can be created, taking the result modulo 10^9 + 7. For example, when arr = [2, 4], three binary trees can be formed: [2], [4], and [4, 2, 2].

Examples

Example 1

Input: arr = [2,4]

Output: 3

We can make these trees: [2], [4], [4, 2, 2]

Example 2

Input: arr = [2,4,5,10]

Output: 7

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.

Solution Approach

Array Scanning and Hash Table

The problem can be solved by scanning through the array and utilizing a hash table to store the possible values of each node. This allows us to check for potential child nodes whose product equals the parent node’s value, effectively building the tree structure in a bottom-up manner.

Dynamic Programming

A dynamic programming approach is used to store the number of ways each number in the array can form a tree. By iterating over the sorted array, we progressively calculate the possible binary trees that can be formed with each number, relying on previously computed results.

Modulo Operation for Large Numbers

Given the potential for large numbers in the calculation, it is necessary to take the result modulo 10^9 + 7. This ensures that intermediate and final results remain manageable and within the problem's constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the number of elements in the array and the operations for checking factor relationships. A straightforward approach using dynamic programming with hash lookups will have a time complexity of O(n^2), where n is the size of the array. Space complexity is O(n) due to the hash table storing intermediate results for each element.

What Interviewers Usually Probe

Ability to optimize with dynamic programming and hash table lookups.
Understanding of modular arithmetic in large number problems.
Clear explanation of array scanning and the trade-off between time and space complexity.

Common Pitfalls or Variants

Common pitfalls

Forgetting to use modulo 10^9 + 7 when calculating the result.
Inefficient solutions due to improper handling of array scanning and hash lookups.
Confusing non-leaf nodes' product with other types of tree structures, leading to incorrect tree construction.

Follow-up variants

Modifying the problem to allow repeated elements in the array.
Adding constraints where each node can only appear a limited number of times in the tree.
Changing the rules such that non-leaf nodes' values must not equal the product of their children.

FAQ

What is the key pattern in the Binary Trees With Factors problem?

The primary pattern is array scanning combined with hash lookups, which allows dynamic programming to efficiently count possible binary tree formations.

How does dynamic programming help in solving the Binary Trees With Factors problem?

Dynamic programming helps by storing the number of ways each integer can form a tree, making the solution more efficient by reusing previously calculated results.

Why do we need to take results modulo 10^9 + 7?

Taking results modulo 10^9 + 7 ensures that numbers do not become too large to handle, which is especially important for large input sizes.

What is the time complexity of the Binary Trees With Factors problem?

The time complexity of the optimal solution is O(n^2), where n is the number of elements in the array. This is due to the nested iteration and hash table lookups.

What are the common pitfalls in solving the Binary Trees With Factors problem?

Common pitfalls include forgetting to apply the modulo operation and inefficient handling of array scanning and hash lookups, which can lead to incorrect solutions.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)
        arr.sort()
        idx = {v: i for i, v in enumerate(arr)}
        f = [1] * n
        for i, a in enumerate(arr):
            for j in range(i):
                b = arr[j]
                if a % b == 0 and (c := (a // b)) in idx:
                    f[i] = (f[i] + f[j] * f[idx[c]]) % mod
        return sum(f) % mod

Continue Practicing

#792 number of matching subsequences #1048 longest string chain #833 find and replace in string