369. Largest Divisible Subset
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 any order. If there are multiple solutions, return any one of them.
Note: As there can be multiple correct answers, the compiler returns 1 if the answer is valid, else 0.
Example 1:
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.
Example 2:
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.
Now Your Turn!
Pick the correct output for the given inputInput: nums = [7, 14, 28, 3]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= nums.length <= 103
- 1 <= nums[i] <= 106