Largest Divisible Subset Problem


Description

LeetCode Problem 368.

Given a set of distinct positive integers 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, or
  • answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Example 1:

1
2
3
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

1
2
Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2 * 10^9
  • All the integers in nums are unique.


Sample C++ Code

Dynamic programming approach:

  1. We first sort the array so that we only have to check A[i] % A[j] when j < i.
  2. The vector dp[i] is the longest subset that satisfies the required conditions and ending at index i. The initial length of any subset is 1.
  3. The vector previous_index[i] stores the indices of previously included elements in this subset.
  4. For j < i < n, if A[i] % A[j] == 0 and dp[i] < dp[j] + 1, we add A[i] to the subsets that have last element as A[j].
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
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& A) {
		int n = A.size();

		if(n == 0) return {};

		sort(A.begin(), A.end());

		vector<int> dp(n, 1);
		vector<int> previous_index(n, -1);

		int max_ind = 0; 

		for(int i=1; i<n; i++) {
		   for(int j=0; j<i; j++) {
		       if(A[i]%A[j]==0 and dp[i] < dp[j] + 1) {
		           dp[i] = dp[j]+1;
		           previous_index[i] = j;
		       }
		   }
		   if(dp[i] > dp[max_ind]) {
		       max_ind = i;
		   }
		}
		        
		vector<int> answer;
		int t = max_ind;  
		while(t >= 0) {
		  answer.push_back(A[t]);
		  t = previous_index[t];
		}

		return answer;  
    }
};




Related Posts

Palindromic Substrings Problem

LeetCode 647. Given a string s, return the number of...

Largest Plus Sign Problem

LeetCode 764. You are given an integer n. You have...

K Inverse Pairs Array Problem

LeetCode 629. For an integer array nums, an inverse pair...

Domino And Tromino Tiling Problem

LeetCode 790. You have two types of tiles, a 2...

Decode Ways II Problem

LeetCode 639. A message containing letters from A-Z can be...