Leetcode 823. Binary Trees With Factors

Problem Explanation

In this problem, we're provided an array of unique integers, where each integer is greater than 1. The task is to create binary trees using these integers. However, there are two important rules to keep in mind:

1. We could repeat an integer any number of times.
2. Each non-leaf node's value should be equal to the product of the values of its children.

The goal is to calculate total number of possible binary trees following these rules that we can build and return that number modulo 10 ** 9 + 7.

For example: If we have the integers [2, 4], we could build three different binary trees: [2], [4], [4, 2, 2], where [4, 2, 2] is a binary tree with 2 as left and 2 as right child of 4 .

This problem requires good understanding of dynamic programming and hash maps.

Solution Approach

1. The solution begins with the sorting of the array and initializing a hash map and a dynamic programming (dp) array. The dp array initially has all elements as 1, representing the possibility of single node tree. The hash map stores an integer in the array as key and its index in the array as value.

2. Then, we walk through the sorted array, and for each element, we iterate through all the elements before it. Here, the current element acts as a root and the previous elements act as a left child.

3. If the current element (root) is divisible by the previous element (left child), we find the right child as the root divided by left child. If this right child is also present in the array, we add the product of the number of binary trees possible with the left and right child to the number of binary trees possible with the root node. This is done to account for the new trees formed with the root, left child and right child.

4. The number of binary trees possible with each element as root is stored in dp array, and finally the sum of all the elements of dp array modulo 10 ** 9 + 7 gives the required answer.

Python Solution

1
2python
3class Solution:
4    def numFactoredBinaryTrees(self, arr):
5        dp = {}
6        for a in sorted(arr):
7            dp[a] = sum(dp[b] * dp.get(a / b, 0) for b in arr if b < a)
8            dp[a] += 1
9        return sum(dp.values()) % (10**9+7)

Java Solution

1
2java
3class Solution {
4    public int numFactoredBinaryTrees(int[] arr) {
5        long res = 0L, mod = (long)1e9+7;
6        Arrays.sort(arr);
7        HashMap<Integer, Long> dp = new HashMap<>();
8        for (int i = 0; i < arr.length; ++i) {
9            dp.put(arr[i], 1L);
10            for (int j = 0; j < i; ++j)
11                if (arr[i] % arr[j] == 0) 
12                    dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.getOrDefault(arr[i] / arr[j], 0L)) % mod);
13            res = (res + dp.get(arr[i])) % mod;
14        }
15        return (int)res;
16    }
17}

JavaScript Solution

1
2javascript
3var numFactoredBinaryTrees = function(arr) {
4    let MOD = Math.pow(10, 9) + 7;
5    let N = arr.length;
6    arr.sort((a, b) => a - b);
7
8    let dp = new Array(N).fill(0);
9    let index = {};
10    for (let i = 0; i < N; ++i)
11        index[arr[i]] = i;
12
13    for (let i = 0; i < N; ++i) {
14        dp[i] = 1;
15        for (let j = 0; j < i; ++j)
16            if (arr[i] % arr[j] === 0)
17                dp[i] = (dp[i] + dp[j] * dp[index[arr[i] / arr[j]]] || 0) % MOD;
18    }
19
20    return dp.reduce((a, b) => (a + b) % MOD, 0);
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int numFactoredBinaryTrees(vector<int>& arr) {
6        sort(begin(arr), end(arr));
7        unordered_map<int, long> dp;
8        for (int i = 0; i < arr.size(); i++) {
9            dp[arr[i]] = 1;
10            for (int j = 0; j < i; j++)
11                if (arr[i] % arr[j] == 0)
12                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[arr[i] / arr[j]]) % int(1e9 + 7);
13        }
14        return accumulate(begin(dp), end(dp), 0L, [](long s, auto &p) { return (s + p.second) % int(1e9 + 7); });
15    }
16};

C# Solution

1
2csharp
3public class Solution 
4{
5    public int NumFactoredBinaryTrees(int[] arr) 
6    {
7        Array.Sort(arr);
8        long[] dp = new long[arr.Length];
9        int MOD = (int)Math.Pow(10,9) + 7;
10        for (int i=0;i<arr.Length;i++)
11        {
12            dp[i] = 1;
13            for (int j=0;j<i;j++)
14                if (arr[i]%arr[j] == 0)
15                    dp[i] = (dp[i] + dp[j]*dp[Array.IndexOf(arr, arr[i]/arr[j])])%MOD;
16        }
17        return (int)(dp.Sum()%MOD);
18    }
19}

In all of these solutions, the concept of Dynamic Programming is used where we remember the previously computed values, which helps us avoid repeated calculations. This makes the algorithm more efficient. Hope, this gives clear understanding of problem and it's solutions.### Ruby Solution

1
2ruby
3class Solution
4  def num_factored_binary_trees(arr)
5      sorted_array = arr.sort_by!(&:to_i)
6      dp = Hash[sorted_array.zip([1]*arr.length)]
7      sorted_array.each do |num|
8          dp[num] = dp.each do |k, v|
9              next 1 if k >= num
10              next (dp[k] * dp[num/k.to_i]) if num%k == 0 && dp[num/k.to_i]
11          end.sum % (1e9 + 7)
12      end
13      dp.values.sum % (1e9 + 7)
14  end
15end

In the Ruby solution, we follow the same concept of Dynamic Programming is used, where we remember the previously computed values to avoid repeated calculations.

Scala Solution

1
2scala
3object Solution {
4    def numFactoredBinaryTrees(arr: Array[Int]): Int = {
5        val MOD: Int = 1000000007
6        val dp = Array.ofDim[Long](arr.length)
7        val index = scala.collection.mutable.HashMap[Int, Int]()
8        arr = arr.sorted
9        for (i <- arr.indices) {
10            dp(i) = 1
11            index(arr(i)) = i
12            for (j <- 0 until i)
13                if (arr(i) % arr(j) == 0) dp(i) = (dp(i) + dp(j) * dp(index.getOrElse(arr(i)/arr(j), 0)) % MOD).toLong
14        }
15        (dp.sum % MOD).toInt
16    }
17}

The Scala solution also uses the Dynamic Programming concept to remember the previously computed values, avoiding repeated calculations. This makes the algorithm more efficient.

Haskell Solution

1
2haskell
3import Data.List
4import qualified Data.IntMap as M
5
6numFactoredBinaryTrees :: [Int] -> Int
7numFactoredBinaryTrees arr = sum dp `mod` modNum
8  where sorted = sort arr
9        indexed = zip [0..] sorted
10        mapped = M.fromList $ map (\(i, n) -> (n, i)) indexed
11        dp = [sum [dp !! j * M.findWithDefault 0 (div i j) mapped | j <- takeWhile (<= div i 2) sorted] `mod` modNum + 1 | i <- sorted]
12        modNum = 10^9 + 7

In the Haskell solution, we create a map of values of ‘arr’ to their indices. The DP array ‘dp’ helps in maintaining the count of possible trees for each value being a root. We iterate through each value and check all possible pairs which would result in a product equal to that value. In the end, we return the sum of all possible trees for each value as root after taking it modulo 10**9+7.

By implementing the steps discussed above, we can successfully solve the problem in all the provided programming languages. The main key to solving this problem is understanding the rules and using dynamic programming effectively.