https://leetcode.com/problems/largest-divisible-subset

First of all, notice, that if we need to find 3 numbers given properties, than if we put then in decreasing order a > b > c, than it is sufficient and enough that a%b = 0 and b%c=0, then it is automatically a%c=0.

Let us know sort our number and in sol[i] list keep the best solution, where the biggest number is equal to nums[i]. How can we find it? Look at all smaller numbers and if nums[i] is divisible by this smaller number, we can update solution. Let us go through example: nums = [4,5,8,12,16,20].

  1. sol[0] = [4], the biggest divisible subset has size 1.
  2. sol[1] = [5], because 5 % 4 != 0.
  3. sol[2] = [4,8], because 8 % 4 = 0.
  4. sol[3] = [4,12], because 12 % 4 = 0.
  5. sol[4] = [4,8,16], because 16 % 8 = 0 and 16 % 4 = 0 and we choose 8, because it has longer set.
  6. sol[5] = [4,20] (or [5,20] in fact, but it does not matter). We take [4,20], because it has the biggest length and when we see 5, we do not update it.
  7. Finally, answer is [4,8,16].

Complexity: time complexity is O(n^2), because we fist sort our numbers and then we have double loop. Space complexity also potentially O(n^2), but for big n, length of the longest subset will not be more than 32: (each time you new number will be at least twice bigger than previous, so there will be maximum 32 numbers in our set) so so we can say it is O(32n).

Possible improvements

Note similarity of this problem with problem 300 Longest Increasing Subsequence, however it is different, and we can not apply O(n log n) algorighm here directly, when we add new number we can not use binary search. There is idea by @yanrucheng with comlexity O(nlogn + n*sqrt(V)), where V is the biggest number. I am interested, if there is O(n log n) solution here? If you know such method please let me know!

class Solution:
    def largestDivisibleSubset(self, nums):
        if len(nums) == 0: return []
        nums.sort()
        sol = [[num] for num in nums]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0 and len(sol[i]) < len(sol[j]) + 1:
                    sol[i] = sol[j] + [nums[i]]
        return max(sol, key=len)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0368