LeetCode. Largest Divisible Subset

Problem:

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

 

Example 1:

Input: [1,2,3]

Output: [1,2] (of course, [1,3] will also be ok)

 

Example 2:

Input: [1,2,4,8]

Output: [1,2,4,8]

 

-Summary-

1. Sort the input nums list (*Sorting is important in this implementation)

2. Using the python generator and dp double list, we store the maximum length where list of first index that can divide the current number without a remainder.

3. return the longest list in the dp.

 

ex) Input: [1,4,2,6,7]

sort --> [1,2,4,6,7]

1. dp = [[]]

2. dp = [[], [1]]

3. dp = [[], [1], [2,1]]

4. dp = [[], [1], [2,1], [4,2,1]] --> since 4 is divisible by 2 and [2,1] is maximum length of the list, we append to dp.

5. dp = [[], [1], [2,1], [4,2,1], [6,2,1]] --> since 6 is not divisible by 4 and [2,1] is maximum length of the list, we append to dp.

6. dp = [[], [1], [2,1], [4,2,1], [6,2,1], [7,1]] --> since 7 is not divisible by 6, 4 and 2. only divisible number is 1. Therefore, we append [7,1].

 

If we do not sort,  the process will be as below:

ex) Input: [3,4,16,8]

1. dp = [[]]

2. dp = [[], [3]]

3. dp = [[], [3], [4]]

4. dp = [[], [3], [4], [16,4]]

5. dp = [[], [3], [4], [16,4], [8,4]]

 

return [16,4] <--Wrong. Answer should be [16,8,4].

Complexity:

Time complexity: O(n^2) --> sort nums +  a double loop to find and max element.

Space complexity: O(n^2)--> dp --> list of list  

 

풀면서 많이 헤맸고, discussion의 도움을 받아 풀수 있었다. 아직도 python generator 와 list comprehension이 익숙하지 않지만 문제를 풀면서 계속 배우는것 같다.

 

https://wiki.python.org/moin/Generators

Generators - Python Wiki

https://stackoverflow.com/questions/12920214/python-for-syntax-block-code-vs-single-line-generator-expressions

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]