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


Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)



Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]



Credits:Special thanks to @Stomach_ache for adding this problem and creating all test cases.

Difficulty: interview

Starter code:

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

Solutions:
from math import sqrt
 class Solution:
     def largestDivisibleSubset(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         nums.sort()
         l, prev = {}, {}  # length, previous number(largest divisor in nums)
         max_l, end_number = 0, None
         
         for i in nums:
             tmp_l, tmp_prev = 0, None
             for j in range(1, 1 + int(sqrt(i))):
                 if i % j == 0:
                     tmp = i // j
                     if tmp in prev and l[tmp] > tmp_l:
                         tmp_l, tmp_prev = l[tmp], tmp
                     if j in prev and l[j] > tmp_l:
                         tmp_l, tmp_prev = l[j], j                    
                     
             tmp_l += 1
             prev[i], l[i] = tmp_prev, tmp_l
             
             if tmp_l > max_l:
                 max_l, end_number = tmp_l, i
         
         ans = []
         while end_number is not None:
             ans.append(end_number)
             end_number = prev[end_number]
         
         return ans