binary-trees-with-factors

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of unique integers, <code>arr</code>, where each integer <code>arr[i]</code> is strictly greater than <code>1</code>.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node&#39;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 <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: <code>[2], [4], [4, 2, 2]</code></pre>

Example 2:

<pre>
Input: arr = [2,4,5,10]
Output: 7
Explanation: We can make these trees: <code>[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]</code>.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>2 &lt;= arr[i] &lt;= 109</code></li>
	<li>All the values of <code>arr</code> are unique.</li>
</ul>

numFactoredBinaryTrees

Binary Trees With Factors

Array

Hash Table

Dynamic Programming

Sorting

给出一个含有不重复整数元素的数组 <code>arr</code> ，每个整数 <code>arr[i]</code> 均大于 1。

用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？答案可能很大，返回 对 <code>109 + 7</code> 取余 的结果。

&nbsp;

示例 1:

<pre>
输入: <code>arr = [2, 4]</code>
输出: 3
解释: 可以得到这些二叉树: <code>[2], [4], [4, 2, 2]</code></pre>

示例 2:

<pre>
输入: <code>arr = [2, 4, 5, 10]</code>
输出: <code>7</code>
解释: 可以得到这些二叉树: <code>[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]</code>.</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>2 &lt;= arr[i] &lt;= 109</code></li>
	<li><code>arr</code> 中的所有值 互不相同</li>
</ul>