Largest Divisible Subset

LeetCode Problem #368 (Medium)

Problem Statement

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, returning any subset is fine.

Testcases

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]

Problem Explanation

From a given set of unique positive integers, we must compare pairs of elements to see if either of the integers are divisible by the other. If the condition is satisfied, we create a subset with these integers. We must return the longest possible subset which can satisfy this condition.

Example:

Consider the input array as: [1, 2, 3]

1 % 2 != 0, 2 % 1 = 0 (satisfied)
1 % 3 != 0, 3 % 1 = 0 (satisfied)
2 % 3 != 0, 3 % 2 != 0 (not satisfied)
Possible subsets: [1, 2], [1, 3]

Prerequisite Knowledge

Subset

A subset is a set of zero or more elements which is contained within a larger set of elements. The definition of a subset does not stipulate that the subset must maintain the relative order of the original set. That is, the order of the elements in the subset does not have to be sequentially equivalent to the set from which it has been derived.

Example

Let us consider the string "coding".

The sequence of elements in this string is as follows:

c o d i n g
1 2 3 4 5 6

A subset of the characters from the original set must contain only characters which belong to the original set but does not have to maintain the relative order in which they are present in that set.

Correct Subset: [i, o, n]

i o n (valid elements)
4 2 5 

Incorrect Subset: [c, s, n]

c s n (s is not in the original set
1 _ 5 

For a sequence of size n, we can have a total of (2^n) subsets.

Refer to the Prerequisite Knowledge section in Is Subsequence to understand the difference between a subsequence and a subset:

Is Subsequence

Dynamic Programming

Refer to the Prerequisite Knowledge section in Coin Change 2:

Coin Change 2

Algorithm

Bottom-Up DP Approach

1. Calculate the size of the input array and check if it is empty.

2. Sort the array in ascending order such that we only have to compare the value of nums[j] % nums[i] and not nums[i] % nums[j].

3. Create a vector to build the DP table with the length of the longest subset.

4. Create a vector to store and track the indices of previous elements in a subset such that when we build a bigger subset, we can include those elements.

5. Iterate through the input array such that j < i < n and add nums[i] to the subset if and only if:

   a. nums[i] % nums[j] == 0

   b. If nums[i] is added to the subset which ends with nums[j], the length of the new subset is greater than the current subset.

6. Keep track of the previous indices in each iteration and the maximum index value.

7. Create a resultant vector to build the longest subset using the maximum index value and previous indices.

Time Complexity: O(m*n)

Code

vector<int> largestDivisibleSubset(vector<int>& nums) {
    int size = nums.size();
    
    if(size == 0) {
        return {};
    }
        
    // Sort the input vector such that i < j, so that we only have to compare nums[j] % nums[i]
    sort(nums.begin(), nums.end());
    
    // Create a vector to store the length of the longest substring
    // The initial length of any subset is 1
    vector<int> dp(size, 1);
    
    // Create a vector to store the indices of previously included elements in a subset which is being expanded
    vector<int> previous(size, -1);
    
    // Create a variable to keep track of the index of the longest substring
    int max = 0;
    
    // Iterate through the array elements such that j < i < n
    for(int i = 1; i < size; i++) {
        for(int j = 0; j < i; j++) {
            // If nums[i] % nums[j] = 0 and if the length of the subset ending with nums[j] becomes greater than the existing subset after adding nums[i]
            // We can add nums[i] to a subset with the last element being nums[j]
            if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                // Keep track of previous indices of i
                previous[i] = j;
            }
        }
        // Update the maximum index value
        if(dp[i] > dp[max]) {
            max = i;
        }
    }
    // Use a resultant vector to build the final subset
    vector<int> result;
    int index = max;
    while(index >= 0) {
        result.push_back(nums[index]);
        index = previous[index];
    }
    return result;
}