#823

Binary Trees With Factors

specialist · 825 · lc medium +31 · verified · 53.1% accepted · 3,369 likes · top 44%

Description

You are given an array of unique integers arr, each strictly greater than 1.

Using these integers, construct binary trees where every non-leaf node's value equals the product of its two children's values. Each integer may be used any number of times.

Return the total number of such binary trees, modulo 10⁹ + 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].

Code

1

2

3

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int: