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 <= 103
1 <= nums[i] <= 106
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.
