Problem Description
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 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 10^9 + 7.
Key Insights
- Each number can be a leaf node or can represent a product of its children.
- A node can be formed if it can be expressed as a product of two numbers in the array.
- Dynamic programming can be utilized to keep track of the number of trees that can be formed using each number as a root.
- The problem can be approached by sorting the array to ensure that we only consider valid children for each node.
Space and Time Complexity
Time Complexity: O(n^2)
Space Complexity: O(n)
Solution
To solve the problem, we can use dynamic programming with the following steps:
- Sort the input array to facilitate finding valid pairs (factors).
- Use a dictionary to map each integer in the array to the number of unique trees that can be formed with that integer as a root.
- For each integer in the sorted array, check every possible factorization into two integers that are also in the array. For each valid factorization, update the count of trees that can be formed.
- The final answer will be the sum of all counts of trees formed by each integer modulo
10^9 + 7.