☕ DSA Java Articles

Topics › Dynamic Programming › DP on LIS

Largest Divisible Subset

Medium TUF ID 603 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a set of distinct positive integers nums, return a largest subset in which every pair (x, y) satisfies x % y == 0 or y % x == 0; that is, of any two chosen numbers, one divides the other. If several subsets have the maximum size, any of them is accepted.

Constraints: 1 ≤ n ≤ 1000, 1 ≤ nums[i] ≤ 2 × 10^9, all values distinct. The Java file returns an empty list for an empty array and returns the subset in ascending order.

Example 1

nums = [1, 2, 3]
answer = [1, 2]     // [1, 3] is equally valid; 2 and 3 cannot both be chosen

Example 2

nums = [1, 16, 7, 8, 4]
answer = [1, 4, 8, 16]

Although the problem says “subset”, it is secretly a subsequence problem. Once the numbers are sorted, a divisible subset is a chain in which each number divides the next, which is the Longest Increasing Subsequence with a different comparison.

The key observation

Sort the values. Take any divisible subset and list it in ascending order: c1 < c2 < ... < cm. Every pair is divisible, so in particular each c_t divides c_{t+1}. Conversely, if each element divides the next, then by transitivity of divisibility (a | b and b | c imply a | c) every earlier element divides every later one, so the whole set is pairwise divisible.

So “pairwise divisible” collapses to a condition on neighbours only. That is the same shape as LIS, where “increasing” is checked between neighbours and transitivity of < takes care of the rest. Sorting fixes the order, so the smaller number of each pair always comes first and we only test larger % smaller == 0.

Approach 1: Brute force

Intuition. Try every subset of the sorted array (as a bitmask), check the neighbour condition on the chosen elements, and keep the largest valid one. Skipping masks that are not larger than the current best saves time but does not change the exponential bound.

Algorithm.

  1. Sort a copy of the array.
  2. For each mask from 1 to 2^n - 1 with more bits than the best so far, walk its chosen indices in order and check that each chosen value divides the next chosen value.
  3. Return the values of the best mask.
static List<Integer> bruteForce(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length, bestMask = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        if (Integer.bitCount(mask) <= Integer.bitCount(bestMask)) continue;
        int prev = -1;
        boolean ok = true;
        for (int i = 0; i < n && ok; i++) {
            if ((mask >> i & 1) == 0) continue;
            if (prev != -1 && a[i] % a[prev] != 0) ok = false;      // consecutive chosen values must divide
            prev = i;
        }
        if (ok) bestMask = mask;
    }
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < n; i++) if ((bestMask >> i & 1) == 1) res.add(a[i]);
    return res;
}

Complexity. Time O(2^n · n), space O(n). Usable only for tiny n; the tests use it as a reference.

Approach 2: Optimal, LIS-style DP with parent pointers

Intuition. After sorting, let dp[i] be the size of the largest divisible chain that ends at a[i]. Such a chain is either a[i] alone, or a chain ending at some earlier a[j] that divides a[i], extended by a[i]. We do not need to check a[i] against every member of that chain: all of them divide a[j], and a[j] divides a[i], so all of them divide a[i]. Therefore

dp[i] = 1 + max(dp[j]) over j < i with a[i] % a[j] == 0   (or 1 if no such j)

To output the subset itself, store parent[i] = j for the j that gave the maximum (and parent[i] = i for a chain that starts at i). Track last, an index with the largest dp, and follow the parents back.

Algorithm.

  1. Sort a copy a of the input.
  2. For each i: dp[i] = 1, parent[i] = i; for each j < i with a[i] % a[j] == 0 and dp[j] + 1 > dp[i], set dp[i] = dp[j] + 1 and parent[i] = j. Update last if dp[i] is a new maximum.
  3. Starting at last, collect a[last] and move to parent[last] until an index is its own parent. Reverse the list.
static List<Integer> optimal(int[] nums) {
    int n = nums.length;
    List<Integer> res = new ArrayList<>();
    if (n == 0) return res;
    int[] a = nums.clone();
    Arrays.sort(a);
    int[] dp = new int[n], parent = new int[n];                     // dp[i] = largest chain ending at a[i]
    int last = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        parent[i] = i;
        for (int j = 0; j < i; j++) {
            if (a[i] % a[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > dp[last]) last = i;
    }
    res.add(a[last]);
    while (parent[last] != last) {
        last = parent[last];
        res.add(a[last]);
    }
    Collections.reverse(res);
    return res;
}

Dry run on nums = [1, 16, 7, 8, 4], sorted to a = [1, 4, 7, 8, 16]:

i a[i] earlier divisors (dp) dp[i] parent[i]
0 1 none 1 0
1 4 1 (1) 2 0
2 7 1 (1) 2 0
3 8 1 (1), 4 (2) 3 1
4 16 1 (1), 4 (2), 8 (3) 4 3

last = 4; the walk visits 16 → 8 → 4 → 1, reversed to [1, 4, 8, 16].

Complexity. Time O(n^2) for the double loop plus O(n log n) for sorting. Space O(n) for dp, parent and the sorted copy.

Why sorting is required. Without it, a chain could need a later element to divide an earlier one, and the “extend a chain ending at j < i” step would miss it. For [4, 2, 8], unsorted processing would compare 2 only with 4, see that 4 does not divide 2, and never discover the chain 2, 4, 8 in the right order. Sorting puts every chain in ascending order, which is also the order of indices.

Edge cases and pitfalls