# Find Largest Divisble Subset…-FcukTheCode

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.

``````Input: [1,2,3]

Output: [1, 2]``````
```def largestSb(arr, n):
arr.sort(reverse = False)
Dcount = [1 for i in range(n)]
Pcount = [-1 for i in range(n)]

maxi = 0
for i in range(1,n):
for j in range(i):
if (arr[i] % arr[j] == 0):
if (Dcount[i] < Dcount[j] + 1):
Dcount[i] = Dcount[j]+1
Pcount[i] = j
if (Dcount[maxi] < Dcount[i]):
maxi = i

k = maxi
L=[]
while (k >= 0):
L.append(arr[k])
k = Pcount[k]
return sorted(L)

arr=list(map(int,input('Set of +ve integers : ').split(' ')))
print(largestSb(arr,len(arr)))```

Input_1:
Set of +ve integers : 1 2 3

Output:
[1, 2]

Input_2:
Set of +ve integers : 1 2 4 8

Output:
[1, 2, 4, 8]

Input_3:
Set of +ve integers : 1 2 3 4 6 24

Output:
[1, 2, 4, 24]

Input_4:
Set of +ve integers : 5 9 18 54 108 540 90 180 360 720

Output:
[9, 18, 90, 180, 360, 720]

Input_5:
Set of +ve integers : 4 8 10 240

Output:
[4, 8, 240]

Input_6:
Set of +ve integers : 2 3 4 8

Output:
[2, 4, 8]

ILLUSTRATION