Binary Trees With Factors
MediumAsked by:
61 views
Topics:
ArraysDynamic Programming
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] <= 109- All the values of
arrare unique.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range of values for the integers in the input array?
- Can the input array contain duplicate numbers, and if so, how should that affect the count of binary trees?
- If the input array is empty or cannot form any binary trees with the given constraints, what should the function return?
- Is the input array guaranteed to be sorted?
- How large can the input array be?
Brute Force Solution
Approach
The basic idea is to try every possible way to build the binary trees. For each number in the input, we'll consider it as the root, and then exhaustively try all possible pairs of smaller numbers to be its children.
Here's how the algorithm would work step-by-step:
- For each number in our set, consider it as the top (root) of a potential tree.
- Find all pairs of numbers in the original set that when multiplied together, give you the root number.
- For each of these pairs, consider them as the left and right children of the root.
- If we can build a valid tree this way, count it.
- Repeat this process for every number as a potential root.
- Make sure that each valid tree is counted only once, even if it can be built in different ways.
- The total number of valid trees is the answer.
Code Implementation
def binary_trees_with_factors_brute_force(numbers):
number_set = set(numbers)
count = 0
for root_value in numbers:
count += count_trees(root_value, number_set)
return count
def count_trees(root_value, number_set):
tree_count = 1
# Iterate through possible left children
for left_child in number_set:
# Iterate through possible right children
for right_child in number_set:
# Check if the children multiply to the root
if left_child * right_child == root_value:
# Recursively calculate number of trees
tree_count += 1
return tree_count
def binary_trees_with_factors(numbers):
number_set = set(numbers)
# Dictionary to store number of trees for each number.
tree_counts = {}
numbers.sort()
for number in numbers:
tree_counts[number] = 1
# Find potential children for current number
for left_child in numbers:
# If left child is greater, no possible match
if left_child >= number:
break
if number % left_child == 0:
right_child = number // left_child
# Ensure that right_child is in number_set
if right_child in number_set:
# Update number of trees for this number
tree_counts[number] += tree_counts[left_child] * tree_counts[right_child]
total_trees = 0
for number in tree_counts:
total_trees += tree_counts[number]
return total_trees % (10**9 + 7)Big(O) Analysis
Time Complexity
O(n^2) – The algorithm iterates through each number in the input array of size n, considering it as the root of a potential binary tree. For each potential root, it iterates through all possible pairs of numbers in the input to check if their product equals the root. This pair checking involves a nested loop, effectively resulting in checking on the order of n^2 pairs for each root. Thus, the overall time complexity is dominated by this nested loop within the outer loop considering each number as the root, approximating n * n/2 operations, which simplifies to O(n^2).
Space Complexity
O(N) – The provided plain English explanation suggests considering each number in the input as a potential root and finding pairs. This implies the use of a data structure, likely a hash map or a similar data structure, to store the number of ways to form a tree with each number as the root. Since we iterate through all N numbers in the input array and potentially store data about each number, the auxiliary space required to store these intermediate results scales linearly with the number of input elements, N. Therefore, the space complexity is O(N).
Optimal Solution
Approach
This problem asks us to find how many binary trees we can make using a given set of numbers, where each number is the product of its two children. The most efficient strategy involves building up solutions from smaller numbers to larger numbers, remembering previous results to avoid recalculating.
Here's how the algorithm would work step-by-step:
- First, ensure the given numbers are in increasing order. This will help us build trees in a bottom-up fashion.
- Create a way to remember how many trees we can make with each number as the root. Think of this as a way to store successful tree counts for each number.
- For each number in the sorted list, try to find two smaller numbers in the list that multiply to give it. These two smaller numbers will be potential children for the tree with the current number as the root.
- If you find such a pair of children, multiply the number of trees possible for each child (which you've already stored) to get the number of trees possible for the current root using that specific child combination.
- Add up all the tree counts from all the successful child combinations for the current number to get the total number of trees possible with that number as the root. Store this total.
- Finally, sum up the tree counts for all the numbers in the list. This gives you the total number of binary trees that can be formed using the given numbers following the problem's rules.
Code Implementation
def binary_trees_with_factors(array_of_numbers):
array_of_numbers.sort()
number_of_trees = {}
modulo = 10**9 + 7
# Initialize each number as a single-node tree
for number in array_of_numbers:
number_of_trees[number] = 1
for i, root_value in enumerate(array_of_numbers):
for j in range(i):
left_child = array_of_numbers[j]
if root_value % left_child == 0:
right_child = root_value // left_child
# Check if the right child exists in the array
if right_child in number_of_trees:
# Accumulate number of trees formed
number_of_trees[root_value] += (number_of_trees[left_child] * number_of_trees[right_child])
number_of_trees[root_value] %= modulo
# Sum up all possible trees for the final answer
total_trees = 0
for tree_count in number_of_trees.values():
total_trees += tree_count
total_trees %= modulo
return total_treesBig(O) Analysis
Time Complexity
O(n²) – Sorting the input array of size n takes O(n log n) time, but it is dominated by the nested loops that follow. For each of the n numbers in the sorted list, we iterate through the list again to find potential children. This nested iteration results in approximately n * n/2 comparisons to check for factor pairs. Therefore, the overall time complexity is dominated by the nested loop, resulting in O(n²).
Space Complexity
O(N) – The algorithm utilizes a hash map (or dictionary) to store the number of trees that can be formed with each number as the root. Since there will be one entry in the hash map for each number in the input array, and the input array has N elements, the hash map will store N key-value pairs. Therefore, the auxiliary space required is proportional to the size of the input array, N. Thus, the space complexity is O(N).
Edge Cases
| Case | How to Handle |
|---|---|
| Empty or null input array | Return 0 as there are no trees that can be formed. |
| Array with one element | Return 1 as the single element forms a tree of size 1. |
| Array contains the value 0 | Multiplication involving zero will always result in zero, so the algorithm should handle 0 appropriately, likely by not considering it as a factor unless zero is the root. |
| Array contains only the value 1 | The number of trees will be n, where n is the length of the input array. |
| Integer overflow when calculating the number of trees | Use modulo arithmetic (10^9 + 7) as required by the problem statement during multiplication to prevent overflow. |
| Array contains large numbers that could lead to intermediate overflow when multiplied | Ensure the data type used to store intermediate products can accommodate the maximum possible product of two elements in the array or use modulo operation during calculations. |
| No valid trees can be formed from the input array | The algorithm should return 0 as the number of possible trees. |
| Input array is already sorted | The dynamic programming approach should still function correctly and produce the expected result, without requiring additional handling. |
Empty or null input array
How to Handle:
Return 0 as there are no trees that can be formed.
Array with one element
How to Handle:
Return 1 as the single element forms a tree of size 1.
Array contains the value 0
How to Handle:
Multiplication involving zero will always result in zero, so the algorithm should handle 0 appropriately, likely by not considering it as a factor unless zero is the root.
Array contains only the value 1
How to Handle:
The number of trees will be n, where n is the length of the input array.
Integer overflow when calculating the number of trees
How to Handle:
Use modulo arithmetic (10^9 + 7) as required by the problem statement during multiplication to prevent overflow.
Array contains large numbers that could lead to intermediate overflow when multiplied
How to Handle:
Ensure the data type used to store intermediate products can accommodate the maximum possible product of two elements in the array or use modulo operation during calculations.
No valid trees can be formed from the input array
How to Handle:
The algorithm should return 0 as the number of possible trees.
Input array is already sorted
How to Handle:
The dynamic programming approach should still function correctly and produce the expected result, without requiring additional handling.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
