Largest Divisible Subset

By | July 5, 2016
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

leetcode 368.

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]

Solution is from here. This is actually a DP problem, a sort of like minimum coin problem. Have an array count[] to count the max number of element in subset this an element can belong First, sort the array. Then loop the array in ascending order. For each element right, try to see if any element left is divisible by right: nums[right] % nums[left] == 0,  besides, see if count[left] + 1 > count[right]

So the formula will look like:

count[right] = max{count[right], count[left] + 1 if nums[right] % nums[left] == 0}

In the algorithm, we should still use a parent[] to record where it jumps from.

Check my code on github.

public static List<Integer> largestDivisibleSubset(int[] nums) {
    if (nums.length <= 0) {
        return new ArrayList<Integer>();
    }
    int[] parent = new int[nums.length], count = new int[nums.length];
    Arrays.sort(nums);
    int maxPos = 0; // where the max number in the result subset
    for (int right = 0; right < nums.length; right++) {
        parent[right] = -1;
        count[right] = 1;
        for (int left = 0; left < right; left++) {
            if (nums[right] % nums[left] == 0 && count[left] + 1 > count[right]) {
                parent[right] = left;
                count[right] = count[left] + 1;
                if (count[right] > count[maxPos]) { // update max pos
                    maxPos = right;
                }
            }
        }
    }
    List<Integer> ans = new ArrayList<>();
    while (maxPos != -1) {
        ans.add(nums[maxPos]);
        maxPos = parent[maxPos];
    }
    return ans;
}