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
![](http://www.fcukthecode.com/wp-content/uploads/2021/12/Screenshot-from-2021-12-15-20-08-53.png)
More Q
- Determine if a person could attend all meetings in given interval times.
- Find the volume of a volley ball
- Find the maximum score obtained at the end of colour chess grid game.
- Find the number of pairs if positive integers with condition is even.
- Return the largest subset such that every pair meets the given condition.
- Find the number of index triplets that satisfy given condition.
- Handling multiple queries using array – sum, update, range.
- Find all the sequences that occur more than once in DNA molecule.
- Find the biggest number.
- Sum of cube of each number is again equal to the number then it is an Armstrong number.
- Hello World.
- Calculate the Cube Root.
- Find the count of consecutive 1’s present in array.
- Return an array with athletes relative ranks according to the score.
- Return a string of its base 7 representation.
- Return kth largest element in sorted order.
- Find all repeated elements in the array.
- Find atleast one duplicate number in the array.
- Find the maximum result of = a XOR b.