Leetcode 823: Binary Trees With Factors
Given an array of unique integers, where each integer is greater than 1, we can create a binary tree using these integers. The value of each non-leaf node must be the product of the values of its children. The goal is to return the number of distinct binary trees that can be constructed. Since the result may be large, return the answer modulo 10^9 + 7.
Problem
Approach
Steps
Complexity
Input: The input consists of a single array of unique integers, arr, where each integer is strictly greater than 1.
Example: Input: arr = [3, 6]
Constraints:
• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 10^9
• All the values of arr are unique.
Output: The output should be an integer representing the number of distinct binary trees that can be constructed, modulo 10^9 + 7.
Example: Output: 5
Constraints:
• The output must be an integer.
Goal: To solve this problem, we need to calculate the number of valid binary trees that can be formed by using the integers from the input array. The non-leaf nodes should be the product of their children, and each integer in the array can be used multiple times.
Steps:
• Step 1: Sort the array of integers.
• Step 2: Use dynamic programming to calculate the number of valid binary trees for each number in the array, considering that each number can be the product of other integers in the array.
• Step 3: Use a map to store the number of binary trees for each number. For each number, check if it can be the product of any two smaller numbers in the array, and update the count accordingly.
• Step 4: Return the sum of all the counts modulo 10^9 + 7.
Goal: The problem involves calculating the number of binary trees that can be formed from the integers in the array, with constraints on the input size and integer values.
Steps:
• The algorithm should handle input arrays of size up to 1000 efficiently.
• The solution must be efficient given that integer values can go up to 10^9.
Assumptions:
• The input array contains unique integers, and each integer is greater than 1.
• The binary tree structure allows for repeated use of the integers from the array.
• Input: Input: arr = [3, 6]
• Explanation: In this case, the number of distinct binary trees that can be constructed is 5. The possible trees are [3], [6], [3, 3, 3], [6, 3, 2], and [6, 2, 3].
• Input: Input: arr = [2, 4, 5, 10]
• Explanation: Here, the possible binary trees are: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], and [10, 5, 2]. The total count is 7.
Approach: The approach involves using dynamic programming to count the number of binary trees that can be made from each number in the array. By considering each number as a possible root and checking for valid products among smaller numbers, we can efficiently compute the solution.
Observations:
• We need to calculate how many ways we can factor each number in the array using smaller numbers from the array.
• Dynamic programming is ideal for this problem since we can build the solution incrementally by considering smaller subproblems first.
Steps:
• Step 1: Sort the input array to ensure that we process smaller numbers first.
• Step 2: For each number in the array, initialize its count as 1 (itself being a valid tree).
• Step 3: For each pair of smaller numbers that can multiply to give the current number, update the count of binary trees that can be formed with the current number as the root.
• Step 4: Sum the counts for all numbers in the array and return the result modulo 10^9 + 7.
Empty Inputs:
• The problem does not have empty input cases since the array always contains at least one element.
Large Inputs:
• The solution should handle arrays with up to 1000 elements efficiently.
Special Values:
• Consider cases where the array has only one element, or where no valid products can be formed.
Constraints:
• The solution must compute the result efficiently even for large arrays and large integer values.
int numFactoredBinaryTrees(vector<int>& arr) {
sort(arr.begin(), arr.end());
unordered_map<int, long> rootWithCount;
rootWithCount[arr[0]] = 1;
for(int i = 0; i < arr.size(); i++) {
long count = 1;
for(auto j : rootWithCount) {
int root = j.first;
if((arr[i] % root == 0) && (rootWithCount.find(arr[i]/root) != rootWithCount.end())) {
count += rootWithCount[root] * rootWithCount[arr[i]/root];
}
}
rootWithCount[arr[i]] = count;
}
int no = 0;
for(auto it: rootWithCount) no = (no + it.second) % (int)(1e9+7);
return no;
}
1 : Function Definition
int numFactoredBinaryTrees(vector<int>& arr) {
The function `numFactoredBinaryTrees` is defined to take an array `arr` as input, where each element represents a potential factor to form binary trees.
2 : Sorting
sort(arr.begin(), arr.end());
The array `arr` is sorted in ascending order, which helps in ensuring that smaller numbers (potential roots) are considered first when counting possible trees.
3 : Map Initialization
unordered_map<int, long> rootWithCount;
An unordered map `rootWithCount` is initialized to store the number of binary trees that can be rooted at each element in the array.
4 : Base Case
rootWithCount[arr[0]] = 1;
The first element in the sorted array is initialized with a count of 1, meaning that it can form one tree by itself.
5 : Outer Loop
for(int i = 0; i < arr.size(); i++) {
The loop iterates over each element `arr[i]` in the sorted array, calculating how many binary trees can be rooted at that element.
6 : Count Initialization
long count = 1;
A variable `count` is initialized to 1, representing the minimum number of binary trees that can be rooted at `arr[i]` (itself as a single node tree).
7 : Inner Loop
for(auto j : rootWithCount) {
This inner loop iterates over the map `rootWithCount` to check which previously encountered roots can combine with `arr[i]` to form a binary tree.
8 : Root Assignment
int root = j.first;
The `root` variable is assigned the key from the map `rootWithCount`, representing a previously encountered potential root for binary trees.
9 : Factor Check
if((arr[i] % root == 0) && (rootWithCount.find(arr[i]/root) != rootWithCount.end())) {
This condition checks if `arr[i]` can be factored by the current `root` and if the factor `arr[i] / root` also exists in the map `rootWithCount`.
10 : Count Update
count += rootWithCount[root] * rootWithCount[arr[i]/root];
If the factorization condition holds, the number of binary trees rooted at `arr[i]` is updated by adding the product of the tree counts for `root` and `arr[i] / root`.
11 : Store Result
rootWithCount[arr[i]] = count;
After processing all possible factors, the final count of binary trees rooted at `arr[i]` is stored in the map `rootWithCount`.
12 : Final Result Initialization
int no = 0;
The variable `no` is initialized to 0, which will hold the final result — the total number of binary trees that can be formed.
13 : Final Sum Calculation
for(auto it: rootWithCount) no = (no + it.second) % (int)(1e9+7);
The map `rootWithCount` is iterated over, and the total count of binary trees is calculated by summing up all the values. The result is taken modulo 1e9 + 7 to avoid overflow.
14 : Return Statement
return no;
The final result `no`, which contains the total number of binary trees, is returned.
Best Case: O(n^2), where n is the number of integers in the array.
Average Case: O(n^2), where n is the number of integers in the array.
Worst Case: O(n^2), where n is the number of integers in the array.
Description: The time complexity is quadratic due to the nested loop that checks for factor pairs for each number in the array.
Best Case: O(n), where n is the number of integers in the array, for storing the number of binary trees for each number.
Worst Case: O(n), where n is the number of integers in the array, for storing the number of binary trees for each number.
Description: The space complexity is linear because we need to store the number of valid binary trees for each number.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus