Largest Divisible Subset
OracleThe problem
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.
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]
- 1 <= nums.length <= 103
- 1 <= nums[i] <= 106
cpp
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int> nums) {
}
};java
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
}
}python
class Solution:
def largestDivisibleSubset(self, nums):javascript
class Solution {
largestDivisibleSubset(nums) {
}
}csharp
public class Solution
{
public List<int> LargestDivisibleSubset(int[] nums)
{
}
}go
func largestDivisibleSubset(nums []int) []int {
}Stuck? Show a way to structure it+
- 01Sort ascending so divisors come first
- 02Initialize every length to one and predecessor to itself
- 03Relax from earlier divisible values
- 04Backtrack predecessors from the best endpoint
Reference answer
Then expect these follow-ups
Why does sorting make the DP valid?
Tests: correctness reasoning
How could you tie-break among equal subsets?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question