MediumNo. 0823
Binary Trees With Factors — LeetCode 823 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, Dynamic Programming, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- arr = [2,4]
- Output
- 3
- Explanation
- We can make these trees: [2], [4], [4, 2, 2]
Python solution
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) % modComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 823. Binary Trees With Factors is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0792 | Number of Matching Subsequences | Medium |
| 1048 | Longest String Chain | Medium |
| 2008 | Maximum Earnings From Taxi | Medium |
| 2501 | Longest Square Streak in an Array | Medium |
| 2597 | The Number of Beautiful Subsets | Medium |
| 2713 | Maximum Strictly Increasing Cells in a Matrix | Hard |
Frequently asked questions
- How hard is LeetCode 823. Binary Trees With Factors?
LeetCode 823. Binary Trees With Factors is rated Medium on LeetCode.
- What is the time complexity of LeetCode 823. Binary Trees With Factors?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 823. Binary Trees With Factors?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 823. Binary Trees With Factors cover?
LeetCode 823. Binary Trees With Factors is tagged Array, Hash Table, Dynamic Programming and Sorting on LeetCode.