Largest Divisible Subset

Largest Divisible Subset

1. What is this problem about?

In the Largest Divisible Subset problem, you are given a set of distinct positive integers. You need to find the largest subset such that every pair of elements $(S_i, S_j)$ in that subset satisfies either $S_i \% S_j = 0$ or $S_j \% S_i = 0$. In simpler terms, every number in the subset must be a multiple or a divisor of every other number in that same subset.

2. Why is this asked in interviews?

This Array, Math, Sorting, Dynamic Programming interview pattern is frequently used by companies like Apple, Uber, and Oracle. It tests whether a candidate can recognize that sorting the input simplifies the "divisibility" condition. It also assesses ability to reconstruct a solution from DP state, rather than just returning a maximum length.

3. Algorithmic pattern used

The solution uses Dynamic Programming on a sorted array.

1. Sort the array: If $a < b < c$ and $b \% a = 0$ and $c \% b = 0$, then $c \% a = 0$ is automatically true. Sorting turns the "every pair" condition into a "chain" condition.
2. Define DP state: dp[i] is the size of the largest divisible subset ending at index i.
3. Transition: dp[i] = 1 + max(dp[j]) for all $j < i$ such that arr[i] % arr[j] == 0.
4. Reconstruction: To return the actual subset, keep a parent array to track which j was used to get the max value for dp[i].

4. Example explanation

Input: [1, 2, 4, 8, 7] Sorted: [1, 2, 4, 7, 8]

• dp[0] (1): [1], size 1
• dp[1] (2): 2 % 1 == 0, so [1, 2], size 2
• dp[2] (4): 4 % 2 == 0, so [1, 2, 4], size 3
• dp[3] (7): 7 % 1 == 0, so [1, 7], size 2
• dp[4] (8): 8 % 4 == 0, so [1, 2, 4, 8], size 4 Max size is 4. The subset is [1, 2, 4, 8].

5. Common mistakes candidates make

• Not sorting: Failing to sort the array, which makes the divisibility check much harder and potentially $O(2^N)$.
• Returning only the size: The problem usually asks for the subset itself. Forgetting to implement the "parent" pointer or backtracking logic to reconstruct the subset is a common pitfall.
• Inefficient transitions: Not realizing that for a sorted array, you only need to check if the current number is divisible by the last number added to the subset.

6. Interview preparation tip

Practice "Longest Increasing Subsequence" (LIS) before this problem. Largest Divisible Subset is essentially LIS where the condition "greater than" is replaced by "is a multiple of." Understanding LIS will make this DP approach intuitive.