LeetCode 솔루션 분류

[8/9] 823. Binary Trees With Factors

컨텐츠 정보

본문

Medium
1117128Add to ListShare

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.
Accepted
43,990
Submissions
97,120
태그

관련자료

댓글 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.
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)
        
LeetCode 솔루션 357 / 9 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0