368. Largest Divisible Subset

https://leetcode.com/problems/largest-divisible-subset/

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.

1
2
3
4
5
Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)
1
2
3
4
5
Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

java


https://discuss.leetcode.com/topic/49652/classic-dp-solution-similar-to-lis-o-n-2

Classic DP solution similar to LIS, O(n^2)

Use DP to track max Set and pre index.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
int[] count = new int[n];
int[] pre = new int[n];
Arrays.sort(nums);
int max = 0, index = -1;
for (int i = 0; i < n; i++) {
count[i] = 1;
pre[i] = -1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
if (1 + count[j] > count[i]) {
count[i] = count[j] + 1;
pre[i] = j;
}
}
}
if (count[i] > max) {
max = count[i];
index = i;
}
}
List<Integer> res = new ArrayList<>();
while (index != -1) {
res.add(nums[index]);
index = pre[index];
}
return res;
}
}

https://discuss.leetcode.com/topic/49741/easy-understood-java-dp-solution-in-28ms-with-o-n-2-time

Easy understood Java DP solution in 28ms with O(n^2) time

The basic idea is like:

1
2
3
4
1. Sort
2. Find the length of longest subset
3. Record the largest element of it.
4. Do a loop from the largest element to nums[0], add every element belongs to the longest subset.

The old version cant pass the test case [1,2,4,8,9,72] and [4,8,10,240], thanks for that @Yanning and @svc
Here comes the revised version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
int[] dp = new int[nums.length];
dp[0] = 1;

//for each element in nums, find the length of largest subset it has.
for (int i = 1; i < nums.length; i++){
for (int j = i-1; j >= 0; j--){
if (nums[i] % nums[j] == 0){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}

//pick the index of the largest element in dp.
int maxIndex = 0;
for (int i = 1; i < nums.length; i++){
maxIndex = dp[i] > dp[maxIndex] ? i : maxIndex;
}

//from nums[maxIndex] to 0, add every element belongs to the largest subset.
int temp = nums[maxIndex];
int curDp = dp[maxIndex];
for (int i = maxIndex; i >= 0; i--){
if (temp % nums[i] == 0 && dp[i] == curDp){
res.add(nums[i]);
temp = nums[i];
curDp--;
}
}
return res;
}

https://discuss.leetcode.com/topic/49424/java-solution-in-32ms-o-n-2-time-o-n-space

Java Solution in 32ms O(N^2) time, O(N) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
public int[] largestDivisibleSubset(int[] nums) {
if(nums.length < 2)
return nums;
else{
Arrays.sort(nums);
int[] parent = new int[nums.length];
int[] count = new int[nums.length];
int max = 0, maxind = -1;
for(int i = nums.length - 1; i >= 0; i--){
for(int j = i; j < nums.length; j++){
if(nums[j] % nums[i] == 0 && count[i] < 1 + count[j] ){
count[i] = 1 + count[j];
parent[i] = j;
if(count[i] > max){
max = count[i];
maxind = i;
}
}
}
}
int[] res = new int[max];
for(int i = 0; i < max; i++){
res[i] = nums[maxind];
maxind = parent[maxind];
}
return res;
}
}
}

cpp


https://discuss.leetcode.com/topic/49456/c-solution-with-explanations

C++ Solution with Explanations

The key concept here is:
Given a set of integers that satisfies the property that each pair of integers inside the set are mutually divisible, for a new integer S, S can be placed into the set as long as it can divide the smallest number of the set or is divisible by the largest number of the set.

For example, let’s say we have a set P = { 4, 8, 16 }, P satisfies the divisible condition. Now consider a new number 2, it can divide the smallest number 4, so it can be placed into the set; similarly, 32 can be divided by 16, the biggest number in P, it can also placed into P.

Next, let’s define:

EDIT: For clarification, the following definitions try to enlarge candidate solutions by appending a larger element at the end of each potential set, while my implementation below is prefixing a smaller element at the front of a set. Conceptually they are equivalent but by adding smaller elements at the front saves the trouble for keeping the correct increasing order for the final answer. Please refer to comments in code for more details.

For an increasingly sorted array of integers a[1 .. n]

T[n] = the length of the largest divisible subset whose largest number is a[n]

T[n+1] = max{ 1 + T[i] if a[n+1] mod a[i] == 0 else 1 }

Now, deducting T[n] becomes straight forward with a DP trick. For the final result we will need to maintain a backtrace array for the answer.

Implementation in C++:

对于,从第一个到最后一位的循环,可以考虑是否可以倒着来,倒着或许更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());

vector<int> T(nums.size(), 0);
vector<int> parent(nums.size(), 0);

int m = 0;
int mi = 0;

// for(int i = 0; i < nums.size(); ++i) // if extending by larger elements
for(int i = nums.size() - 1; i >= 0; --i) // iterate from end to start since it's easier to track the answer index
{
// for(int j = i; j >=0; --j) // if extending by larger elements
for(int j = i; j < nums.size(); ++j)
{
// if(nums[i] % nums[j] == 0 && T[i] < 1 + T[j]) // if extending by larger elements
// check every a[j] that is larger than a[i]
if(nums[j] % nums[i] == 0 && T[i] < 1 + T[j])
{
// if a[j] mod a[i] == 0, it means T[j] can form a larger subset by putting a[i] into T[j]
T[i] = 1 + T[j];
parent[i] = j;

if(T[i] > m)
{
m = T[i];
mi = i;
}
}
}
}

vector<int> ret;

for(int i = 0; i < m; ++i)
{
ret.push_back(nums[mi]);
mi = parent[mi];
}

// sort(ret.begin(), ret.end()); // if we go by extending larger ends, the largest "answer" element will come first since the candidate element we observe will become larger and larger as i increases in the outermost "for" loop above.
// alternatively, we can sort nums in decreasing order obviously.

return ret;
}
};

https://discuss.leetcode.com/topic/49456/c-solution-with-explanations/2

T[n] = the length of the largest divisible subset whose largest number is a[n] —- this is not true,

T[n] should be the length of the largest divisible subset whose smallest number is a[n], not largest


python


https://discuss.leetcode.com/topic/49455/4-lines-in-python

4 lines in Python

1
2
3
4
5
def largestDivisibleSubset(self, nums):
S = {-1: set()}
for x in sorted(nums):
S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
return list(max(S.values(), key=len))

My S[x] is the largest subset with x as the largest element, i.e., the subset of all divisors of x in the input. With S[-1] = emptyset as useful base case. Since divisibility is transitive, a multiple x of some divisor d is also a multiple of all elements in S[d], so it’s not necessary to explicitly test divisibility of x by all elements in S[d]. Testing x % d suffices.

While storing entire subsets isn’t super efficient, it’s also not that bad. To extend a subset, the new element must be divisible by all elements in it, meaning it must be at least twice as large as the largest element in it. So with the 31-bit integers we have here, the largest possible set has size 31 (containing all powers of 2).


https://discuss.leetcode.com/topic/49528/python-dp-n-2-solution

Python dp n^2 solution

We first do some math work. For two numbers, A and B, if A < B, A % B must > 0 (A != 0). The only chance A % B == 0 must be A >= B.

With this idea, we sort the list. Then, the question turns similar to no.300 longest increasing subsequence. For ith number, its largest divisible subset is the max of subset of any j from 0 - i-1 in which nums[i] % nums[j] == 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
from copy import copy
nums.sort()
n = len(nums)
if n == 0: return []
dp = [0] * n
dp[0] = [nums[0]]
#print(dp)
for i in xrange(1, n):
curNum = nums[i]
maxSet = []
for j in xrange(i):
if curNum % nums[j] == 0:
localSet = copy(dp[j])
if len(localSet) > len(maxSet):
maxSet = localSet

maxSet.append(nums[i])
dp[i] = maxSet
#print(dp)

#print(dp)
res = []
for localSet in dp:
if len(localSet) > len(res):
res = localSet
return res
谢谢你,可爱的朋友。