{x}
blog image

Binary Trees With Factors

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 <= 1000
  • 2 <= arr[i] <= 109
  • All the values of arr are unique.

Solution Explanation:

This problem asks to count the number of binary trees that can be formed using a given array of unique integers, where each non-leaf node's value is the product of its children's values. The solution utilizes dynamic programming to efficiently calculate the count.

Approach:

  1. Sorting: The input array arr is first sorted in ascending order. This allows us to iterate through the array and efficiently check for factors.

  2. Index Map: A hash map idx is created to store each element of the sorted array and its index. This enables quick lookup of an element's index during factor checking, reducing the time complexity.

  3. Dynamic Programming: A dynamic programming array f is used to store the number of binary trees that can be formed using the elements up to a given index. f[i] represents the number of binary trees that can be formed using arr[i] as the root.

  4. Iteration and Factor Check: The code iterates through the sorted array. For each element a, it checks for factors among elements that have already been processed. If b is a factor of a and a/b is also present in the array, then it means b and a/b can be children of a node with value a.

  5. DP Update: The number of trees with a as the root is updated by summing the number of trees possible using b as the left child and a/b as the right child (f[j] * f[idx[c]]), where j is the index of b and c is a/b.

  6. Modulo Operation: The modulo operator (% mod) is used throughout the calculation to avoid integer overflow.

  7. Summation: Finally, the sum of all elements in f is calculated and returned, representing the total number of possible binary trees.

Time Complexity: O(N^2), where N is the length of the input array. This is because the nested loop iterates through all pairs of elements in the array.

Space Complexity: O(N) to store the array f and the hash map idx.

Code Explanation (Python):

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)}  # Create index map
        f = [1] * n  # Initialize DP array
        for i, a in enumerate(arr):
            for j in range(i):
                b = arr[j]
                if a % b == 0 and (c := (a // b)) in idx: # Check for factors
                    f[i] = (f[i] + f[j] * f[idx[c]]) % mod # Update DP array
        return sum(f) % mod # Return the total count

The other languages (Java, C++, Go, TypeScript) follow the same logic with minor syntax variations. The core dynamic programming and factor checking steps remain consistent across all implementations.