Largest Divisible Subset

Dynamic Programming LIS Easy Go Ad-Free - ₹20/mo

Given an array nums of positive integers, the task is to find the largest subset such that every pair (a, b) of elements in the subset satisfies a % b == 0 or b % a == 0. Return the subset in sorted order. If there are multiple solutions, return any one of them.

Examples:

Input: nums = [3, 5, 10, 20]

Output: [5, 10, 20]

Explanation: The subset [5, 10, 20] satisfies the divisibility condition: 10 % 5 == 0 and 20 % 10 == 0.

Input: nums = [16, 8, 2, 4, 32]

Output: [2, 4, 8, 16, 32]

Explanation: The entire array forms a divisible subset since 32 % 16 == 0, 16 % 8 == 0, and so on.

Input: nums = [7, 14, 28, 3]

Constraints

1 <= nums.length <= 10³
1 <= nums[i] <= 10⁶

Hints

A Dynamic Programming (DP) approach efficiently solves this problem by Sorting nums in ascending order ensures that if nums[j] divides nums[i], then nums[i] is always greater than nums[j].
"Using DP (dp[i]) to track the size of the largest divisible subset ending at index i. Maintaining a parent[] array to reconstruct the subset efficiently."

Editorial

Striver and the team have worked tirelessly over the past few days to bring this to you. Please bear with us a little more as we finalize everything.

Frequently Occurring Doubts

Q: Why is the problem similar to LIS?

A: Both problems track the longest sequence following specific conditions. LIS requires elements to be strictly increasing, while this problem requires elements to be multiples of each other. Instead of dp[i] representing an increasing subsequence length, here it represents the largest divisible subset ending at nums[i].

Q: Can we use a hash set instead of sorting?

A: No, because checking divisibility conditions efficiently requires O(n²) complexity unless we sort nums first. Sorting ensures a greedy-like structure where smaller numbers appear first, reducing unnecessary checks.

Interview Followup Questions

Q: How would you solve this problem in O(n log n) instead of O(n²)?

A: Instead of checking every pair (j, i), use a HashMap (dp[i]) and TreeSet (binary search) to efficiently track divisibility relations. We can optimize subset construction by only storing the smallest valid previous element.

Q: Can this problem be solved using a graph-based approach?

A: Yes! Treat nums as nodes and add edges where a % b == 0. The longest path in this directed graph gives the largest subset.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories