823. Binary Trees With Factors #

Problem #

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] <= 10^9

Problem Summary #

Given an array containing unique integer elements, each integer is greater than 1. We use these integers to construct binary trees, and each integer can be used any number of times. In such a tree, the value of each non-leaf node should be equal to the product of the values of its two child nodes. How many binary trees satisfy the conditions? The returned result should be modulo 10 * 9 + 7.

Solution Ideas #

• The first thought is a brute-force solution: sort first, then traverse all nodes and enumerate combinations where the product of two numbers equals the value of a third node. Then enumerate these combinations and form trees. When counting here, note that if the left and right children are not symmetric, swapping the left and right subtrees is another solution. But this method times out. The reason is that brute force enumerates many repeated nodes and combinations. The way to optimize this is to put already calculated nodes into a map. There are 2 layers of map here. The first layer of map memoizes combinations of pairwise products, using the parent node as the key and the 2 left and right children as the value. The second layer of map memoizes the number of types of binary trees with root as the root node at this time; the key is root, and the value stores the number of types. After this optimization, the DFS brute-force solution can runtime beats 100%.

• Another solution is DP. Define dp[i] as the number of types of trees with i as the root node. dp[i] is initially 1, because every node itself can form a tree with itself as the single node root. Sorting is also needed first. The state transition equation is:

  \[ dp[i] = \sum_{j<i, k<i}^{}dp[j] * dp[k], j * k = i \]

  Finally, accumulate all results in the dp[] array and take the modulo to get the final result. The time complexity is O(n^2), and the space complexity is O(n).

Code #

package leetcode

import (
	"sort"
)

const mod = 1e9 + 7

// Solution 1 DFS
func numFactoredBinaryTrees(arr []int) int {
	sort.Ints(arr)
	numDict := map[int]bool{}
	for _, num := range arr {
		numDict[num] = true
	}
	dict, res := make(map[int][][2]int), 0
	for i, num := range arr {
		for j := i; j < len(arr) && num*arr[j] <= arr[len(arr)-1]; j++ {
			tmp := num * arr[j]
			if !numDict[tmp] {
				continue
			}
			dict[tmp] = append(dict[tmp], [2]int{num, arr[j]})
		}
	}
	cache := make(map[int]int)
	for _, num := range arr {
		res = (res + dfs(num, dict, cache)) % mod
	}
	return res
}

func dfs(num int, dict map[int][][2]int, cache map[int]int) int {
	if val, ok := cache[num]; ok {
		return val
	}
	res := 1
	for _, tuple := range dict[num] {
		a, b := tuple[0], tuple[1]
		x, y := dfs(a, dict, cache), dfs(b, dict, cache)
		tmp := x * y
		if a != b {
			tmp *= 2
		}
		res = (res + tmp) % mod
	}
	cache[num] = res
	return res
}

// Solution 2 DP
func numFactoredBinaryTrees1(arr []int) int {
	dp := make(map[int]int)
	sort.Ints(arr)
	for i, curNum := range arr {
		for j := 0; j < i; j++ {
			factor := arr[j]
			quotient, remainder := curNum/factor, curNum%factor
			if remainder == 0 {
				dp[curNum] += dp[factor] * dp[quotient]
			}
		}
		dp[curNum]++
	}
	totalCount := 0
	for _, count := range dp {
		totalCount += count
	}
	return totalCount % mod
}