Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 368 with 20 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 368 # by problem number
lcpy gen -s largest_divisible_subset # by problem name
nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
answer[i] % answer[j] == 0, oranswer[j] % answer[i] == 0Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
Input: nums = [1,2,4,8]
Output: [1,2,4,8]
1 <= nums.length <= 10001 <= nums[i] <= 2 * 10^9nums are unique.class Solution:
# Time: O(n^2)
# Space: O(n)
def largest_divisible_subset(self, nums: list[int]) -> list[int]:
nums = sorted(nums)
n = len(nums)
dp = [1] * n
parent = [-1] * n
for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
parent[i] = j
best = max(range(n), key=lambda i: dp[i])
chain: list[int] = []
while best != -1:
chain.append(nums[best])
best = parent[best]
return chain[::-1]
| Time | Space |
|---|---|
| O(n^2) | O(n) |