Largest Divisible Subset - Leetcode Solution

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.

1