Largest Divisible Subset Size
01 · Problem
You are given an array nums of distinct positive integers. Pick a subset of these numbers such that for every two numbers x and y in the subset, one of them divides the other (x % y == 0 or y % x == 0).
Return the size of the largest such subset. A subset with a single element always qualifies, so the answer is at least 1.
02 · Examples
nums = [4,8,10,240]
3
{4,8,240} works because 4 divides 8 and 8 divides 240. Adding 10 fails because 10 and 8 do not divide each other.
nums = [3,6,7,12,24]
4
3, 6, 12 and 24 each divide the next one. 7 does not divide or get divided by any of them.
nums = [3,5,7]
1
No two numbers divide each other, so the best subset holds just one element.
03 · Constraints
- 011 <= nums.length <= 1000
- 021 <= nums[i] <= 2 * 109
- 03All values in nums are distinct
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.