LeetCode 823: Binary Trees With Factors

Explanation:

To solve this problem, we can use dynamic programming. We can sort the input array and then for each element, we can find all possible pairs of factors that can form that element. For each pair of factors, we can check if we have already computed the number of binary trees for those factors, and then update the count for the current element.

We can use a hashmap to store the count of binary trees formed by each element. Then, we iterate over the elements to calculate the count of binary trees. Finally, we sum up all the counts to get the total number of binary trees that can be formed.

Algorithm:

1. Sort the input array.
2. Initialize a hashmap to store the count of binary trees formed by each element.
3. Iterate over each element in the input array.
4. For each element, find all possible pairs of factors that can form that element.
5. For each pair of factors, update the count of binary trees formed by the current element.
6. Finally, sum up all the counts to get the total number of binary trees.

Time Complexity: O(n^2) where n is the number of elements in the input array. Space Complexity: O(n) due to the hashmap.

:

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        Map<Integer, Long> dp = new HashMap<>();
        long count = 0;
        int mod = (int) 1e9 + 7;
        
        for (int i = 0; i < arr.length; i++) {
            dp.put(arr[i], 1L);
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0 && dp.containsKey(arr[i] / arr[j])) {
                    dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(arr[i] / arr[j])) % mod);
                }
            }
            count = (count + dp.get(arr[i])) % mod;
        }
        
        return (int) count;
    }
}