823. Binary Trees with Factors

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 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 10^9 + 7.

Examples:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 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 ≤ 1000
• 2 ≤ arr[i] ≤ 10^9
• All the values of arr are unique

Python Solution

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        arr.sort()
        dp = {}
        
        for i, num in enumerate(arr):
            dp[num] = 1  # Tree with single node
            for j in range(i):
                if num % arr[j] == 0:  # arr[j] can be left child
                    right = num // arr[j]
                    if right in dp:  # If right child exists in array
                        dp[num] = (dp[num] + dp[arr[j]] * dp[right]) % MOD
                        
        return sum(dp.values()) % MOD

Implementation Notes:

• Uses dynamic programming to build trees bottom-up
• Sorts array to process smaller numbers first
• Time complexity: O(n²)
• Space complexity: O(n)

Java Solution

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        int MOD = 1_000_000_007;
        Arrays.sort(arr);
        Map dp = new HashMap<>();
        
        for (int i = 0; i < arr.length; i++) {
            dp.put(arr[i], 1L);  // Tree with single node
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0) {  // arr[j] can be left child
                    int right = arr[i] / arr[j];
                    if (dp.containsKey(right)) {  // If right child exists
                        long ways = dp.get(arr[j]) * dp.get(right) % MOD;
                        dp.put(arr[i], (dp.get(arr[i]) + ways) % MOD);
                    }
                }
            }
        }
        
        long sum = 0;
        for (long ways : dp.values()) {
            sum = (sum + ways) % MOD;
        }
        return (int) sum;
    }
}

C++ Solution

class Solution {
public:
    int numFactoredBinaryTrees(vector& arr) {
        const int MOD = 1e9 + 7;
        sort(arr.begin(), arr.end());
        unordered_map dp;
        
        for (int i = 0; i < arr.size(); i++) {
            dp[arr[i]] = 1;  // Tree with single node
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0) {  // arr[j] can be left child
                    int right = arr[i] / arr[j];
                    if (dp.count(right)) {  // If right child exists
                        dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[right]) % MOD;
                    }
                }
            }
        }
        
        long sum = 0;
        for (const auto& pair : dp) {
            sum = (sum + pair.second) % MOD;
        }
        return sum;
    }
};

JavaScript Solution

/**
 * @param {number[]} arr
 * @return {number}
 */
var numFactoredBinaryTrees = function(arr) {
    const MOD = 1e9 + 7;
    arr.sort((a, b) => a - b);
    const dp = new Map();
    
    for (let i = 0; i < arr.length; i++) {
        dp.set(arr[i], 1);  // Tree with single node
        for (let j = 0; j < i; j++) {
            if (arr[i] % arr[j] === 0) {  // arr[j] can be left child
                const right = arr[i] / arr[j];
                if (dp.has(right)) {  // If right child exists
                    const ways = (dp.get(arr[j]) * dp.get(right)) % MOD;
                    dp.set(arr[i], (dp.get(arr[i]) + ways) % MOD);
                }
            }
        }
    }
    
    let sum = 0;
    for (const ways of dp.values()) {
        sum = (sum + ways) % MOD;
    }
    return sum;
};

C# Solution

public class Solution {
    public int NumFactoredBinaryTrees(int[] arr) {
        const int MOD = 1_000_000_007;
        Array.Sort(arr);
        var dp = new Dictionary();
        
        for (int i = 0; i < arr.Length; i++) {
            dp[arr[i]] = 1;  // Tree with single node
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0) {  // arr[j] can be left child
                    int right = arr[i] / arr[j];
                    if (dp.ContainsKey(right)) {  // If right child exists
                        long ways = dp[arr[j]] * dp[right] % MOD;
                        dp[arr[i]] = (dp[arr[i]] + ways) % MOD;
                    }
                }
            }
        }
        
        long sum = 0;
        foreach (var ways in dp.Values) {
            sum = (sum + ways) % MOD;
        }
        return (int)sum;
    }
}

Implementation Notes:

• Uses Dictionary for dynamic programming
• Handles modulo arithmetic for large numbers
• Time complexity: O(n²)
• Space complexity: O(n)