~/leetcode$cat368. Largest-Divisible-Subset

The intuition behind this question is to think of an efficient way to figure out if a number can be added to a subset of numbers while being divisible by / divides the all numbers in the subset.

Clearly, the brute force method of checking all the numbers in the subset is inefficent and would be too slow. Because it seems like it would take at least O(n^2) time to do this, sorting is a viable option (you can sort in O(n log n) time).

If we consider that the subsets are sorted:

• when adding a larger number to the subset, we only need to check that the largest number in the subset divides the new number
• if the new number is divisible by the largest number in the subset, it is guaranteed to be divisible by all the numbers in the subset, assuming that the subset is valid (you can prove this by induction).

Therefore, we can start with an empty subset and iterate through the sorted array, checking if the new number is divisible by the largest number in the subset. If it is, we can make a new subset that is the subset plus the new number. However, implementing this solution is still too slow, and we end up with TLE on leetcode.

To make it more efficient, we can solve this using dynamic programming. We memoize the largest subset that ends in each number in the array.

• Note: I could have used an array with indexes as the keys but I thought it would be easier to use a dictionary with the numbers as the keys because I’m goofy.

• dp[num] is the largest subset that ends with num

• the recurrence becomes:

  • dp[num] = dp[key] + [num] if num % prev_num == 0 and len(dp[num]) < len(dp[key]) + 1
    • where for each number (going from the smallest to the largest), we iterate through all the subsets and make a new subset with each subset + the number
    • we only update the current dp if the new subset is larger than the current subset and the new number divides the largest element in the current subset

At the end, we can iterate through dp and return the largest subset.

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nums.sort()
        subsets = {n: [n] for n in nums}
        for num in nums:
            for key, arr in subsets.items():
                if num == key: continue
                if num % key == 0 and len(subsets[num]) < len(subsets[key]) + 1:
                    subsets[num] = subsets[key] + [num]

        largest = []
        for arr in subsets.values():
            if len(arr) > len(largest):
                largest = arr

        return largest

Time Complexity: O(n^2)

Space Complexity: O(n)

Time Taken: forgot to keep track