Largest Divisible Subset
MediumSort, then LIS with a divisibility test
Problem
Return the largest subset where every pair (a,b) satisfies a%b==0 or b%a==0.
Sort, then build the longest chain where each number divides the next (LIS with divisibility).
The idea
After sorting, a subset is valid when each element divides the next, so it is exactly the LIS recurrence with 'less than' replaced by 'divides'. Sorting is what makes checking only the smaller element sufficient.
The trick
- Sorting first is essential for the transitivity to hold.
- Track predecessors to print the subset.
- O(n²).
Step 1 of 8. Keep the smallest tail for each length. Binary-search each number into "tails". Values: 2, 5, 3, 7, 101, 18.
Replace the first tail ≥ x.
1// keep the smallest possible tail for each length2const tails = [];3for (const x of nums) {4 let lo = 0, hi = tails.length;5 while (lo < hi) { const m=(lo+hi)>>1;6 if (tails[m] < x) lo = m+1; else hi = m; }7 tails[lo] = x;8}9return tails.length;Input
- array
- [2, 5, 3, 7, 101, 18]
Memory
- num
- —
Output
- LIS
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3]
- Output:
- [1, 2]
- Explanation:
- 1,2 (or 1,3) each divide cleanly → size 2.
Example 2
- Input:
- nums = [1, 2, 4, 8]
- Output:
- [1, 2, 4, 8]
- Explanation:
- Every pair divides → whole set.
Example 3
- Input:
- nums = [3]
- Output:
- [3]
- Explanation:
- A single number.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.