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

Example 1:

Input: [1,2,3]
Output: [1,2] or [1,3]

Example 2:

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

Solution #1:

Let’s say we have a list of numbers as shown below.

nums = [1, 2, 3, 4]

First thing to notice is that every integer is its own largest divisible subset if the given condition does not satisfy for any other element in the list. For example, given a list [5, 7] where neither of them are divisible by each other, the largest divisible subset can be [5] or [7], so both are correct.

Keeping that in mind, a straightforward approach is to check every integer with every other integer in the list to see if the condition Si % Sj = 0 or Sj % Si = 0 is satisfied. Before we begin, we sort the given list so that we can avoid having too many enumerations. Let’s understand this using another example as shown below.

[2, 4, 8]

Note that the list above is sorted in ascending order and all the elements form a divisible subset. If we choose to add one more element d to the divisible subset at front or an element D at the end of the list, all we have to check is whether D % 8 == 0 and 2 % d == 0.

At first we place each integer in its own subset. Then, we can iterate through the list using double for loops and whenever a pair satisfies the given condition, we extend the individual subsets. We start with the following subsets.

[{1}, {2}, {3}, {4}]

• Use two pointers i and j where i is used to traverse the sorted list [1, 2, 3, 4]
• Calculate the largest divisible subset that ends at the element at i. Use another pointer j to traverse the list until the index i.
• If the values at i and j satisfy the divisibility condition ie. nums[i] % nums[j] == 0 and if the (size of the subset at i) < (size of subset at j + 1), then extend the subset at i. This is because we want to extend the subset only if we can get another larger subset, otherwise it’s already the largest subset possible ending with element at i.

To understand clearly, check the example walkthrough below.

Once we have all the subsets, we return the one with the max length.

Time Complexity: O(N²) since we use double for loops

Space Complexity: O(N²) for the use of subsets

Code:

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

    if not nums:
        return []

    nums.sort()
    subsets = [{i} for i in nums]

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] % nums[j] == 0 and len(subsets[i]) < len(subsets[j]) + 1:
                subsets[i] = subsets[j] | {nums[i]}

    return max(subsets, key = len)

Hope you enjoyed learning how to solve the largest divisible subset problem. Have a great day!