Largest Divisible Subset

Share

Given a set of distinct positive integers nums, find the largest subset such that every pair (Si, Sj) satisfies Si % Sj == 0 or Sj % Si == 0.

Example 1
Input: [1,2,3] → Output: [1,2]
Example 2
Input: [1,2,4,8] → Output: [1,2,4,8]

Solution Approach

Sort the array. dp[i] = length of largest divisible subset ending at i. parent[] tracks path. When nums[i] % nums[j] == 0, we can extend j's subset.

  • Sort nums.
  • dp[i]=1, parent[i]=-1 initially.
  • For i from 1 to n-1: for j from 0 to i-1: if nums[i]%nums[j]==0 and dp[j]+1>dp[i]: dp[i]=dp[j]+1, parent[i]=j.
  • Find max index, trace back using parent[] to reconstruct subset.
Java
import java.util.*;

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n], parent = new int[n];
        Arrays.fill(dp, 1); Arrays.fill(parent, -1);
        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1; parent[i] = j;
                }
            }
            if (dp[i] > dp[maxIdx]) maxIdx = i;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = maxIdx; i >= 0; i = parent[i]) {
            res.add(nums[i]);
            if (parent[i] == -1) break;
        }
        return res;
    }
}
  • Time Complexity: O(N^2)
  • Space Complexity: O(N)