Solution For Largest Divisible Subset

Problem Description:

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:

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

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

Solution:

To solve this problem we are going to use dynamic programming. Let’s try to identify the optimal substructure and overlapping subproblems in this problem. As we need to find multiple solutions for our problem for any two numbers of the subset, if one divides the other then we’ll add that number in our subset. So, we can start this problem by sorting the numbers in ascending order. And then we need to consider each element one by one and iterate over all the elements before it which can form a divisible subset.

We will start an array “dp” of length n where dp[i] will represent the size of maximum subset which can be formed using the ith element only. We will consider each element as the smallest number and try to create maximum subsets with its help. To do this we need to know which numbers before the current index are its factors. So we will create a variable “max_len” which will stores the maximum size of subset seen so far.

Now, we iterate the array in an outer loop from a 1th index to n-1th index and for each element, we iterate the elements before it in an inner loop and if the current number is a factor of the previous element we will find its corresponding subset length which we will use to form the current subset length. While doing this we will also keep track of the preceding number which formed the largest subset of the current index and its index will be our lookup index for building the largest subset array.

Pseudo-code:

1. Sort the nums array.
2. Declare an array “dp” of size n and initialize all of them to 1.
3. Declare a variable max_len for finding the maximum size of the largest divisible subset.
4. Declare a variable “index” to store the index of the minimum number of the subset.
5. For i = 1 to n-1, We need to iterate over each element of the array.
6. For j = 0 to i-1, we need to iterate over the elements before the current element.
7. If nums[i] % nums[j] == 0, then there is a factor of nums[j] in nums[i],
   a. Check whether dp[j] is greater than 1+dp[i]. If yes, then update dp[i] to the new value i.e., dp[i] = dp[j]+1.
   b. Also keep track of the maximum length found so far in the loop via max_len variable and update the index with minimum number.
8. Return the largest divisible subset from the nums array iteration backwards starting from the index of the minimum number until the maximum length found.

Python Code:

class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:

    if len(nums) == 0: 
        return []

    nums.sort()
    n = len(nums)
    dp = [1]*n
    max_len = 1
    index = 0

    for i in range(1, n):
        for j in range(0, i):
            if nums[i] % nums[j] == 0:
                dp[i] = max(dp[i], dp[j]+1)
                if dp[i]> max_len:
                    max_len = dp[i]
                    index = i

    ans = []
    prev = -1
    while max_len > 0:
        if prev == -1 or nums[prev] % nums[index] == 0 and dp[index] == max_len:
            ans.append(nums[index])
            prev = index
            max_len -= 1
        index -= 1

    return ans[::-1]

Time Complexity: O(n^2), nested loop to iterate over the array.
Space Complexity: O(n), we are creating a dp array and storing only n elements.

Step by Step Implementation For Largest Divisible Subset

class Solution {
    public List 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 res = new ArrayList<>();
        while (index != -1) {
            res.add(nums[index]);
            index = pre[index];
        }
        return res;
    }
}

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        
        # Base case
        if len(nums) == 0:
            return []
        
        # Sort the array in ascending order
        nums.sort()
        
        # Create an array to store the results (one result for each index in nums)
        results = [[] for _ in nums]
        
        # Iterate through each number in nums
        for i in range(len(nums)):
            
            # Iterate through all previous numbers
            for j in range(i):
                
                # If the current number is divisible by the previous number
                if nums[i] % nums[j] == 0:
                    
                    # If the result for the previous number is longer than the result for the current number
                    if len(results[j]) > len(results[i]):
                        
                        # Copy the result for the previous number into the result for the current number
                        results[i] = results[j].copy()
                        
            # Add the current number to the result for the current number
            results[i].append(nums[i])
            
        # Sort the results by length in descending order
        results.sort(key=len, reverse=True)
        
        # Return the first result (which will be the longest result)
        return results[0]

var largestDivisibleSubset = function(nums) {
    if (nums.length == 0) {
        return [];
    }
    // Sort the array in ascending order
    nums.sort((a, b) => a - b);
    
    // Create an array of same size to store the length of the 
    // largest divisible subset at every index 
    let dp = new Array(nums.length).fill(1);
    
    // Variable to store the maximum length till now
    let max = 1;
    
    // Loop through the array from left to right
    for (let i = 1; i < nums.length; i++) {
        // Loop through the array from left to right
        // for every index i, check if there exists an element 
        // j to its left such that nums[j] is a factor of nums[i]
        // and dp[i] can be updated
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        
        // Update max if dp[i] is greater than it
        if (max < dp[i]) {
            max = dp[i];
        }
    }
    
    // Variable to store the index of the element 
    // in nums which forms the largest divisible subset
    let index = -1;
    
    // Variable to store the last element of the 
    // largest divisible subset
    let last = -1;
    
    // Loop through dp array from right to left
    for (let i = nums.length - 1; i >= 0; i--) {
        // If dp[i] is equal to max, it means nums[i] 
        // is the last element of the largest divisible 
        // subset
        if (dp[i] == max) {
            // Update index and last
            index = i;
            last = nums[i];
            
            // Decrease max by 1 as we consider nums[i] as 
            // part of the largest divisible subset
            max--;
        }
    }
    
    // Variable to store the largest divisible subset
    let subset = [];
    
    // Add nums[index] to subset
    subset.push(nums[index]);
    
    // Loop through nums array from index + 1 to nums.length - 1
    for (let i = index + 1; i < nums.length; i++) {
        // If nums[i] is a factor of last, add it to subset
        if (nums[i] % last == 0) {
            subset.push(nums[i]);
            
            // Update last
            last = nums[i];
        }
    }
    
    // Return subset
    return subset;
};

class Solution {
public:
    vector largestDivisibleSubset(vector& nums) {
        int n = nums.size();
        if (n == 0) return {};
        sort(nums.begin(), nums.end());
        vector dp(n, 0);
        vector parent(n, 0);
        int max_ind = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            parent[i] = i;
            for (int j = i-1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            if (dp[i] > dp[max_ind]) {
                max_ind = i;
            }
        }
        vector res;
        while (max_ind != parent[max_ind]) {
            res.push_back(nums[max_ind]);
            max_ind = parent[max_ind];
        }
        res.push_back(nums[max_ind]);
        return res;
    }
};

public IList LargestDivisibleSubset(int[] nums) { // sort the array nums Array.Sort(nums); // create an empty list to store the final result List result = new List(); // create an empty list to store the current subset List subset = new List(); // iterate through the array for (int i = 0; i < nums.Length; i++) { // create an empty list to store the current subset List currentSubset = new List(); // iterate through the array for (int j = i; j < nums.Length; j++) { // if the current element is divisible by the previous element if (nums[j] % nums[i] == 0) { // add the current element to the current subset currentSubset.Add(nums[j]); } // if the current subset is larger than the previous subset if (currentSubset.Count > subset.Count) { // update the previous subset with the current subset subset = currentSubset; } } // if the current subset is larger than the previous subset if (subset.Count > result.Count) { // update the previous subset with the current subset result = subset; } } // return the result return result; }