Array
Hash Table
Dynamic Programming
Sorting
Description
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] <= 109
All the values of arr
are unique .
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def numFactoredBinaryTrees ( self , arr : List [ int ]) -> int :
mod = 10 ** 9 + 7
n = len ( arr )
arr . sort ()
idx = { v : i for i , v in enumerate ( arr )}
f = [ 1 ] * n
for i , a in enumerate ( arr ):
for j in range ( i ):
b = arr [ j ]
if a % b == 0 and ( c := ( a // b )) in idx :
f [ i ] = ( f [ i ] + f [ j ] * f [ idx [ c ]]) % mod
return sum ( f ) % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 class Solution {
public int numFactoredBinaryTrees ( int [] arr ) {
final int mod = ( int ) 1e9 + 7 ;
Arrays . sort ( arr );
int n = arr . length ;
long [] f = new long [ n ] ;
Arrays . fill ( f , 1 );
Map < Integer , Integer > idx = new HashMap <> ( n );
for ( int i = 0 ; i < n ; ++ i ) {
idx . put ( arr [ i ] , i );
}
for ( int i = 0 ; i < n ; ++ i ) {
int a = arr [ i ] ;
for ( int j = 0 ; j < i ; ++ j ) {
int b = arr [ j ] ;
if ( a % b == 0 ) {
int c = a / b ;
if ( idx . containsKey ( c )) {
int k = idx . get ( c );
f [ i ] = ( f [ i ] + f [ j ] * f [ k ] ) % mod ;
}
}
}
}
long ans = 0 ;
for ( long v : f ) {
ans = ( ans + v ) % mod ;
}
return ( int ) ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 class Solution {
public :
int numFactoredBinaryTrees ( vector < int >& arr ) {
const int mod = 1e9 + 7 ;
sort ( arr . begin (), arr . end ());
unordered_map < int , int > idx ;
int n = arr . size ();
for ( int i = 0 ; i < n ; ++ i ) {
idx [ arr [ i ]] = i ;
}
vector < long > f ( n , 1 );
for ( int i = 0 ; i < n ; ++ i ) {
int a = arr [ i ];
for ( int j = 0 ; j < i ; ++ j ) {
int b = arr [ j ];
if ( a % b == 0 ) {
int c = a / b ;
if ( idx . count ( c )) {
int k = idx [ c ];
f [ i ] = ( f [ i ] + 1l * f [ j ] * f [ k ]) % mod ;
}
}
}
}
long ans = 0 ;
for ( long v : f ) {
ans = ( ans + v ) % mod ;
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 func numFactoredBinaryTrees ( arr [] int ) int {
const mod int = 1e9 + 7
sort . Ints ( arr )
f := make ([] int , len ( arr ))
idx := map [ int ] int {}
for i , v := range arr {
f [ i ] = 1
idx [ v ] = i
}
for i , a := range arr {
for j := 0 ; j < i ; j ++ {
b := arr [ j ]
if c := a / b ; a % b == 0 {
if k , ok := idx [ c ]; ok {
f [ i ] = ( f [ i ] + f [ j ] * f [ k ]) % mod
}
}
}
}
ans := 0
for _ , v := range f {
ans = ( ans + v ) % mod
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 function numFactoredBinaryTrees ( arr : number []) : number {
const mod = 10 ** 9 + 7 ;
arr . sort (( a , b ) => a - b );
const idx : Map < number , number > = new Map ();
const n = arr . length ;
for ( let i = 0 ; i < n ; ++ i ) {
idx . set ( arr [ i ], i );
}
const f : number [] = new Array ( n ). fill ( 1 );
for ( let i = 0 ; i < n ; ++ i ) {
const a = arr [ i ];
for ( let j = 0 ; j < i ; ++ j ) {
const b = arr [ j ];
if ( a % b === 0 ) {
const c = a / b ;
if ( idx . has ( c )) {
const k = idx . get ( c ) ! ;
f [ i ] = ( f [ i ] + f [ j ] * f [ k ]) % mod ;
}
}
}
}
return f . reduce (( a , b ) => a + b ) % mod ;
}
GitHub