PPractick

The problem

You're designing a task-scheduling optimizer where jobs have "batch sizes," and a batch of size A can only be merged into a batch of size B if B is an exact multiple of A (this avoids leftover/fractional work when consolidating batches). Given a set of distinct positive integers representing available batch sizes, you want to find the largest group of batch sizes you can chain together for consolidation — where for every pair (a, b) in the chosen group (with a <= b), b is divisible by a.

Example: nums = [1,2,4,8] — the entire set works since 1|2, 2|4, 4|8 (and transitively all pairs divide). Answer: [1,2,4,8].

Function signature

vector<int> largestDivisibleSubset(vector<int>& nums);

Test cases

Input nums	Output (one valid answer)	Explanation
[1,2,3]	[1,2] or [1,3]	Both are valid length-2 divisible subsets; either is acceptable
[1,2,4,8]	[1,2,4,8]	Every pair divides — full set works
[4,8,10,240]	[4,8,240]	`4
[1]	[1]	Single element
[3,5,7]	[3] or [5] or [7]	No two share a divisibility relation — any single element is length 1
[2,3,4,8,16]	[2,4,8,16]	Longest chain skips 3 entirely

(Always confirm: the problem asks for any one valid maximum-size subset when multiple exist — output isn't unique.)

How interviewers phrase it

• "Given a set of distinct positive integers, find the largest subset such that for every pair of elements in it, one divides the other."
• "You just need every pair to satisfy divisibility — figure out how to avoid checking all pairs explicitly."
• May emphasize "return the actual subset" rather than just its size, to test reconstruction skills.

Clarifying questions to ask

1. Are all elements guaranteed distinct? (This problem assumes yes — important because sorting + adjacent-pair divisibility relies on it.)
2. Should I return just the size of the largest subset, or the actual elements?
3. If multiple subsets of the same maximum size exist, is any one of them acceptable, or is there a tie-breaking rule (e.g., lexicographically smallest)?
4. Can the array contain 1? (Special case: 1 divides everything, often the natural starting point of chains.)
5. What's the expected size of nums? (Confirms O(n²) DP is acceptable vs needing something smarter.)

Follow-ups to expect

1. "Why does sorting the array first make this solvable with an O(n²) DP?"
2. "How is this exactly like Longest Increasing Subsequence?"
3. "Can you reconstruct and return the actual subset, not just its length?"
4. "What's the time and space complexity, and can it be improved?"
5. "What if the problem asked for the largest subset where every pair sums to a perfect square, or some other pairwise relation?"
6. "Can two different valid subsets of the same max length both be acceptable, and how would you modify code to return the lexicographically smallest one?"

Related questions

• Longest Increasing Subsequence Medium
• Print Longest Increasing Subsequence Medium
• Longest Increasing Subsequence (DP-43) Medium
• Longest String Chain Medium
• Longest Bitonic Subsequence Medium
• Number of Longest Increasing Subsequences Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in