823. Binary Trees With Factors LeetCode Solution

In this guide, you will get 823. Binary Trees With Factors LeetCode Solution with the best time and space complexity. The solution to Binary Trees With Factors problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Binary Trees With Factors solution in C++
4. Binary Trees With Factors solution in Java
5. Binary Trees With Factors solution in Python
6. Additional Resources

Problem Statement of Binary Trees With Factors

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 <= 1000
2 <= arr[i] <= 109
All the values of arr are unique.

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(n)

823. Binary Trees With Factors LeetCode Solution in C++

class Solution {
 public:
  int numFactoredBinaryTrees(vector<int>& arr) {
    constexpr int kMod = 1'000'000'007;
    const int n = arr.size();
    // dp[i] := the number of binary trees with arr[i] as the root
    vector<long> dp(n, 1);
    unordered_map<int, int> numToIndex;

    ranges::sort(arr);

    for (int i = 0; i < n; ++i)
      numToIndex[arr[i]] = i;

    for (int i = 0; i < n; ++i)  // arr[i] is the root
      for (int j = 0; j < i; ++j)
        if (arr[i] % arr[j] == 0) {  // arr[j] is the left subtree
          const int right = arr[i] / arr[j];
          if (const auto it = numToIndex.find(right); it != numToIndex.cend()) {
            dp[i] += dp[j] * dp[it->second];
            dp[i] %= kMod;
          }
        }

    return accumulate(dp.begin(), dp.end(), 0L) % kMod;
  }
};
/* code provided by PROGIEZ */

823. Binary Trees With Factors LeetCode Solution in Java

class Solution {
  public int numFactoredBinaryTrees(int[] arr) {
    final int kMod = 1_000_000_007;
    final int n = arr.length;
    // dp[i] := the number of binary trees with arr[i] as the root
    long[] dp = new long[n];
    Map<Integer, Integer> numToIndex = new HashMap<>();

    Arrays.sort(arr);
    Arrays.fill(dp, 1);

    for (int i = 0; i < n; ++i)
      numToIndex.put(arr[i], i);

    for (int i = 0; i < n; ++i) // arr[i] is the root
      for (int j = 0; j < i; ++j)
        if (arr[i] % arr[j] == 0) { // arr[j] is the left subtree
          final int right = arr[i] / arr[j];
          if (numToIndex.containsKey(right)) {
            dp[i] += dp[j] * dp[numToIndex.get(right)];
            dp[i] %= kMod;
          }
        }

    return (int) (Arrays.stream(dp).sum() % kMod);
  }
}
// code provided by PROGIEZ

823. Binary Trees With Factors LeetCode Solution in Python

class Solution:
  def numFactoredBinaryTrees(self, arr: list[int]) -> int:
    kMod = 1_000_000_007
    n = len(arr)
    # dp[i] := the number of binary trees with arr[i] as the root
    dp = [1] * n
    arr.sort()
    numToIndex = {a: i for i, a in enumerate(arr)}

    for i, root in enumerate(arr):  # arr[i] is the root
      for j in range(i):
        if root % arr[j] == 0:  # arr[j] is the left subtree
          right = root // arr[j]
          if right in numToIndex:
            dp[i] += dp[j] * dp[numToIndex[right]]
            dp[i] %= kMod

    return sum(dp) % kMod
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.