We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Trees With Factors

Number: 843

Difficulty: Medium

Paid? No

Companies: Bloomberg, Amazon, Adobe

Problem Description

Given an array of unique integers arr where each integer is greater than 1, we are to count the number of binary trees we can form such that for every non-leaf node, its value is equal to the product of the values of its two children. Each number in arr can be used multiple times. Return the result modulo 10^9 + 7.

Key Insights

  • Sort the array to ensure that when processing an element, all potential factors are already processed.
  • Use dynamic programming where each number's count is initially 1 (representing a tree with a single node).
  • For every number, check all smaller numbers to see if they can be factors (i.e., if their product gives the current number).
  • Use a hash set or dictionary for constant time lookups of numbers in the array.
  • When valid factor pairs are found, use the product of the counts representing the number of trees that can form with those factors.
  • Take care of the modulo at every step to prevent overflow.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case where n is the length of arr
Space Complexity: O(n) for storing the dp state and using a dictionary for lookups

Solution

We first sort the array and initialize a dictionary (or equivalent) dp to store the number of trees that can be rooted with each number. Each number starts with a count of 1 since it can form a tree by itself. Then, for each number in the sorted array, iterate over all smaller numbers. If the current number is divisible by the smaller number and the quotient also exists in the dp dictionary, add the product of the two counts to the current dp value. This accounts for trees where the smaller number and its corresponding pair form the children of the current number. Finally, sum all dp values for the answer, taking modulo 10^9 + 7.

Code Solutions

# Python solution with detailed comments
MOD = 10**9 + 7

def numFactoredBinaryTrees(arr):
    # Sort the array to ensure factors come before the product
    arr.sort()
    # Create a dictionary to map array values to the count of trees with root equal to that value
    dp = {}
    for i, num in enumerate(arr):
        # Each number can form a tree on its own
        dp[num] = 1
        # Check each previous number as a potential left child factor
        for j in range(i):
            factor = arr[j]
            if num % factor == 0:
                complement = num // factor
                # If the complement exists in the array, update the dp count
                if complement in dp:
                    dp[num] = (dp[num] + dp[factor] * dp[complement]) % MOD
    # Sum the number of trees for all numbers in the array
    return sum(dp.values()) % MOD

# Example usage:
print(numFactoredBinaryTrees([2,4]))       # Output: 3
print(numFactoredBinaryTrees([2,4,5,10]))    # Output: 7
← Back to All Questions