Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (S_i, S_j) of elements in this subset satisfies:

S_i % S_j = 0 or S_j % S_i = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

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

Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]

 class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
    List<Integer> result = new ArrayList<Integer>();
    if(nums==null||nums.length==0)
        return result;
 
    Arrays.sort(nums);
 
    int[] arr = new int[nums.length];
    int[] index = new int[nums.length];
    Arrays.fill(arr, 1);
    Arrays.fill(index, -1);
 
    int max=0;
    int maxIndex=-1;
 
    for(int i=0; i<arr.length; i++){
        for(int j=i-1; j>=0; j--){
            if(nums[i]%nums[j]==0 && arr[j]+1>arr[i]){
                arr[i]=arr[j]+1;
                index[i]=j;
            }
        }
 
        if(max<arr[i]){
            max=arr[i];
            maxIndex=i;
        }
    }
 
    int i=maxIndex;
    while(i>=0){
        result.add(nums[i]);
        i=index[i];
    }
 
    return result;
}
}

Try it on Leetcode

Here, solution is based on Dynamic Programming and using below 4 steps.

1) Initially sort an array so that all divisors of a number appear before it.

2) Create two arrays arr, index. arr is used for storing divisor count(least will be 1) and index is used for storing all index value(which satisfy the condition Si % Sj==0).

3) max is used for max divisor count and maxIndex is used to store the maximum index.

4) Finally using those index value we are returning largest divisible subset numbers.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation

Click here for June Month challenges with solution and explanation

Subscribe us to receive updates instantly.

Please let us know about your views in comment section.

Happy Coding...😍