Menu Close

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

Executed using python3