algoadvance

Leetcode 823. Binary Trees With Factors

Problem Statement

We are given an array arr of unique integers where each integer arr[i] is greater than 1. We need to find how many binary trees we can build where every node is a non-leaf node and its value can be formed by multiplying the values of two child nodes. Each value in the array arr can be used multiple times in the binary tree. The answer should be returned modulo (10^9 + 7).

Constraints:

Clarifying Questions

  1. Can a single value form a tree by itself?
    • No, each value must be a product of two child nodes.
  2. Are repeated values in the tree allowed if they are in the input array?
    • Yes, values may be reused in different trees as long as they form valid structures.
  3. Should the root value also be part of the initial input array?
    • Yes, all node values including the root must be part of the input array.

Strategy

  1. Sort the array: We shall start by sorting the array to easily find valid factors for each value.
  2. Dynamic Programming and HashMap for Counting:
    • Use a hashmap (dp) where dp[x] will store the number of ways to form the value x.
    • Initialize dp[x] = 1 for all x in arr initially since each value itself can form one tree.
  3. Populate DP Table:
    • For each element x in arr and for each y such that y*y <= x:
      • Check if x % y == 0 and (x // y) is also in arr.
      • Update dp[x] by adding the products dp[y] * dp[x // y].
      • If y and x // y are distinct, add the same product again (for y, x // y pairs).
  4. Calculate the Result: Sum all values in dp and return modulo (10^9 + 7).

Code

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class BinaryTreesWithFactors {
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        long mod = 1_000_000_007;
        Map<Integer, Long> dp = new HashMap<>();
        
        for (int a : arr) {
            dp.put(a, 1L); // Initialize each element to have one way to be a single node tree
        }
        
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (arr[i] % arr[j] == 0) {  // arr[j] should be a factor of arr[i]
                    int right = arr[i] / arr[j];
                    if (dp.containsKey(right)) {
                        dp.put(arr[i], (dp.get(arr[i]) + dp.get(arr[j]) * dp.get(right)) % mod);
                    }
                }
            }
        }
        
        long result = 0;
        for (long val : dp.values()) {
            result = (result + val) % mod;
        }
        
        return (int) result;
    }

    public static void main(String[] args) {
        BinaryTreesWithFactors solution = new BinaryTreesWithFactors();
        int[] arr = {2, 4};
        System.out.println(solution.numFactoredBinaryTrees(arr)); // Output: 3
        
        arr = new int[]{2, 4, 5, 10};
        System.out.println(solution.numFactoredBinaryTrees(arr)); // Output: 7
    }
}

Time Complexity

Therefore, the overall time complexity is (O(n^2)), which should be efficient enough given the constraints (with (n) up to 1000).

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