algoadvance

Leetcode 823. Binary Trees With Factors

Problem Statement

Given an array of unique integers, arr, where each integer arr[i] is greater than 1, we want to determine the number of binary trees we can form. Each integer in the array can be a tree node, and for each possible tree node, the tree’s value at that node must equal the product of elements from the array present in its left and right subtrees. Return the number of possible binary trees modulo (10^9 + 7).

Clarifying Questions

Before we dive into solving the problem, let’s clarify a few points:

  1. What is the maximum length of the array?
    • This will help us understand if the proposed solution will be efficient enough.
  2. Will the array always be sorted?
    • If not, should we sort it first?
  3. Are the products of the integers also guaranteed to be in the array?
    • This will influence our approach to forming trees.
  4. What are the constraints on the input values?
    • Knowing this can help us predict any possible edge cases.

Initial Assumptions Based on Standard Constraints

Given these, let’s outline the strategy to derive the solution.

Strategy

  1. Sort the Array:
    • To make the search for factors easier, we sort the array.
  2. Dynamic Programming with a Dictionary:
    • Use a hash map (dictionary) to store the number of ways to form each number as a root by considering each possible pair of nodes (left and right subtrees).
    • The idea is to iterate over each number and attempt to build trees using previous numbers (since the array is sorted).
  3. Consider All Pairs:
    • For each number x in the sorted array, iterate through all smaller numbers y. If x % y == 0 and x / y is also in the array, this implies y * (x / y) = x, we can form a tree with y as one subtree and x / y as the other.
  4. Use Modulo Operation:
    • Since the results can be very large, take results modulo (10^9 + 7).

Time Complexity

The time complexity will primarily be driven by the nested iteration through pairs of numbers, which gives us:

Given the constraints, this approach should be efficient enough.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    int numFactoredBinaryTrees(std::vector<int>& arr) {
        const int MOD = 1'000'000'007;
        std::sort(arr.begin(), arr.end());
        std::unordered_map<int, long> dp;
        long result = 0;
        
        for (int i = 0; i < arr.size(); ++i) {
            dp[arr[i]] = 1; // Each number can form a tree by itself
            for (int j = 0; j < i; ++j) {
                if (arr[i] % arr[j] == 0) {
                    int other = arr[i] / arr[j];
                    if (dp.find(other) != dp.end()) {
                        dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[other]) % MOD;
                    }
                }
            }
            result = (result + dp[arr[i]]) % MOD;
        }
        
        return (int)result;
    }
};

Here we go through the array and use a map to store the number of ways each number can form a tree, iterating over possible pairs of factors. This solution leverages sorting and dynamic programming to efficiently compute the result.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI