LeetCode 솔루션 분류
[8/9] 823. Binary Trees With Factors
본문
Medium
1117128Add to ListShareGiven 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 <= 10002 <= arr[i] <= 109- All the values of
arrare unique.
Accepted
43,990
Submissions
97,120
태그
#Amazon
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 164 ms, faster than 98.48% of Python3 online submissions for Binary Trees With Factors.
Memory Usage: 14.3 MB, less than 30.81% of Python3 online submissions for Binary Trees With Factors.
Memory Usage: 14.3 MB, less than 30.81% of Python3 online submissions for Binary Trees With Factors.
import math
class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
arr.sort()
root_map = {}
res = 0
for num in arr:
limit = math.sqrt(num)
way_num = 1
for root_a in arr:
if root_a > limit: break
root_b = num/root_a
if root_b in root_map:
way_num += root_map[root_a] * root_map[root_b] *
(1 if root_a == root_b else 2)
root_map[num] = way_num
res += way_num
return res % (10**9+7)
