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 <= 10002 <= arr[i] <= 109arr are unique.This approach involves using dynamic programming with a hashmap (or dictionary) to keep track of the number of ways a particular element can be the root of binary trees. We first sort the array, and then for each element, we iterate over all previous elements to find pairs that multiply to the element of interest. For each valid pair, we update the number of trees using previously computed results for the factors.
The function first sorts the array to ensure that for every element we can look back and find previous elements that might form factors. We then use dynamic programming to keep track of the number of trees that can be formed with each element as the root. A nested loop considers each possible pair to check if their product matches the current element and updates the possible combinations using previously computed values. The result is computed modulo 10^9 + 7.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the length of the array, due to the nested loops evaluating possibilities.
Space Complexity: O(n), for storing the dp table.
Leetcode 823. Binary Trees With Factors #Binary Tree #Leetcode #823 • Code with Alisha • 7,053 views views
Watch 9 more video solutions →Practice Binary Trees With Factors with our built-in code editor and test cases.
Practice on FleetCode