Largest Divisible Subset

📋

Problem

Imagine you have a collection of files with sizes, and you want to find the largest group where each file size divides the next one perfectly, ensuring compatibility in a chain.

Given a set of distinct positive integers nums, find the largest subset such that for every pair (Si, Sj) in the subset, either Si % Sj == 0 or Sj % Si == 0. Return the largest subset. If there are multiple answers, return any of them.

1 ≤ nums.length ≤ 10^51 ≤ nums[i] ≤ 10^9All elements of nums are distinct

Edge cases: Single element array → output is the element itselfArray with all prime numbers → output is any single elementArray with multiple chains of same length → output any largest chain

</>

IDE

def largestDivisibleSubset(nums: list[int]) -> list[int]:public List<Integer> largestDivisibleSubset(int[] nums)vector<int> largestDivisibleSubset(vector<int>& nums)function largestDivisibleSubset(nums)

def largestDivisibleSubset(nums: list[int]) -> list[int]:
    # Write your solution here
    pass

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> largestDivisibleSubset(vector<int>& nums) {
    // Write your solution here
    return {};
}

function largestDivisibleSubset(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 3]Greedy approach picking first divisible pair without checking all chains.✅ Use DP to track longest divisible subset ending at each element by checking all previous elements.

Wrong: [2, 4, 8]Fails to include smaller elements like 1 that extend chain length.✅ Sort input and consider all elements from smallest to largest for chain building.

Wrong: []Fails to handle empty or single-element input properly.✅ Add base case checks for empty input and return input itself if length is 1.

Wrong: [2, 3, 5, 7, 11]Returns entire input without checking divisibility, ignoring problem constraints.✅ Check divisibility condition for every pair; if none divides another, return any single element.

Wrong: TLE or timeoutUsing brute force exponential approach instead of DP.✅ Implement O(n^2) DP with sorting to handle large inputs efficiently.

✓

Test Cases

Handle empty and single-element inputs carefully to avoid crashes.

Beware of greedy traps; consider all previous elements for DP updates.

Brute force won't scale; implement DP with sorting for performance.

t1_01basic

Input{"nums":[1,2,3]}

Expected[1,2]

⏱ Performance - must finish in 2000ms

1 divides 2, so [1, 2] is a valid divisible subset. [1, 3] is also valid but same size. Largest size is 2.

💡 Sort the array to build chains from smaller to larger numbers.

💡 Use dynamic programming to track the longest divisible chain ending at each element.

💡 For each number, check previous numbers that divide it and extend the longest chain.

Why it failed: Returned subset missing valid divisible pairs or smaller than max size. Fix by sorting and using DP to build longest divisible chain.

✓ Correctly found largest divisible subset using sorting and DP.

t1_02basic

Input{"nums":[1,2,4,8]}

Expected[1,2,4,8]

⏱ Performance - must finish in 2000ms

All numbers form a chain where each divides the next, so the largest subset is the entire array.

💡 Check if each number divides the next after sorting.

💡 Build the longest chain by extending subsets where divisibility holds.

💡 Return the chain with maximum length after processing all elements.

Why it failed: Subset returned is not the longest chain or misses divisibility. Fix by ensuring DP updates max chain length correctly.

✓ DP correctly identifies the full chain as largest divisible subset.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array should return empty subset.

💡 Handle empty input as a base case.

💡 Return empty list immediately if input is empty.

💡 Check for n=0 and return [] without further processing.

Why it failed: Code crashes or returns non-empty for empty input. Fix by adding base case for empty input.

✓ Correctly returns empty subset for empty input.

t2_02edge

Input{"nums":[7]}

Expected[7]

⏱ Performance - must finish in 2000ms

Single element array returns the element itself as largest divisible subset.

💡 Single element always forms a valid divisible subset.

💡 Check if code handles n=1 correctly.

💡 Return input array itself if length is 1.

Why it failed: Fails to return single element subset or returns empty. Fix by handling single element base case.

✓ Correctly returns single element subset.

t2_03edge

Input{"nums":[2,3,5,7,11]}

Expected[2]

⏱ Performance - must finish in 2000ms

All primes, no number divides another, so largest subset size is 1, any single element is valid.

💡 If no divisibility chain longer than 1 exists, return any single element.

💡 Check divisibility condition carefully for all pairs.

💡 Return the first element or any single element if no chain found.

Why it failed: Returns subset larger than 1 without divisibility or empty subset. Fix by ensuring divisibility check is correct.

✓ Correctly returns single element subset when no divisibility chain exists.

t3_01corner

Input{"nums":[1,3,6,24,36,72]}

Expected[1,3,6,24,72]

⏱ Performance - must finish in 2000ms

Largest divisible subset chains 1 divides 3 divides 6 divides 24 divides 72. 36 breaks chain length.

💡 Sorting helps build chains but check all previous elements for divisibility.

💡 DP must consider all valid predecessors, not just the immediate previous.

💡 Update dp[i] = max(dp[j] + 1) for all j < i where nums[i] % nums[j] == 0.

Why it failed: Greedy approach picking only immediate previous divisible element fails. Fix by checking all previous elements for max chain.

✓ DP correctly finds longest chain by checking all valid predecessors.

t3_02corner

Input{"nums":[1,2,4,8,16,3,6,12]}

Expected[1,2,4,8,16]

⏱ Performance - must finish in 2000ms

Multiple chains of same length exist; largest divisible subset is one of the longest chains.

💡 Multiple chains can have same max length; returning any is valid.

💡 Ensure DP tracks max length and reconstructs one valid chain.

💡 Backtrack from max dp value to build subset.

Why it failed: Fails to return a largest chain or returns smaller chain. Fix by reconstructing chain from dp max index.

✓ Correctly returns one of the largest divisible subsets.

t3_03corner

Input{"nums":[1000000000,500000000,250000000,125000000]}

Expected[125000000,250000000,500000000,1000000000]

⏱ Performance - must finish in 2000ms

Large numbers with gaps still form a divisible chain; test for overflow or incorrect divisibility.

💡 Use 64-bit integers or appropriate types to avoid overflow.

💡 Check divisibility carefully with large numbers.

💡 Sorting and DP logic remains same regardless of magnitude.

Why it failed: Incorrect divisibility due to overflow or wrong modulo operation. Fix by using correct data types and modulo checks.

✓ Correctly handles large numbers and finds largest divisible subset.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n^2) DP must complete within 2 seconds time limit.

💡 DP solution has O(n^2) time complexity.

💡 Brute force exponential solutions will time out here.

💡 Optimize by early breaks or pruning if possible.

Why it failed: TLE due to exponential or inefficient approach. Fix by implementing O(n^2) DP with sorting.

✓ Solution runs within time limit using O(n^2) DP approach.

Practice

1. What is the time complexity of the optimal backtracking with bitmask and memoization solution for the Matchsticks to Square problem, where n is the number of matchsticks?

medium

A. O(4^n) because each stick can go to one of four sides

B. O(n * 2^n) due to exploring subsets with bitmask and pruning repeated states

C. O(n^2) because of sorting and nested loops

D. O(2^n) ignoring the linear factor from iterating over sticks

Solution

1. Step 1: Identify state space size

   The algorithm explores subsets represented by bitmasks, so there are 2^n states.

2. Step 2: Consider per-state work

   For each state, it iterates over n sticks to try adding one stick, leading to O(n * 2^n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask states times linear iteration per state [OK]

Hint: Bitmask states times linear iteration per state [OK]

Common Mistakes:

• Confusing 4^n with 2^n
• Ignoring linear factor n
• Assuming sorting dominates complexity

2. Examine the following buggy code snippet from the trie-based solution. Which line contains the subtle bug that causes incorrect counts for some puzzles?

medium

A. Line where node.count is incremented

B. Line missing filtering words with more than 7 unique letters before insertion

C. Line checking if bit is set in mask during insertion

D. Line checking if puzzle_mask contains child bit during dfs

Solution

1. Step 1: Identify filtering step

   The code inserts all words regardless of unique letter count, causing large trie and slow traversal.

2. Step 2: Understand impact

   Words with >7 unique letters cannot match puzzles (7 letters max), so filtering them out is necessary for correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Filtering missing leads to incorrect counts and performance issues [OK]

Hint: Filter words with >7 unique letters before insertion [OK]

Common Mistakes:

• Not filtering large words
• Incorrect bit checks
• Misplaced count increments

3. Identify the bug in the following code snippet that generates subsets iteratively:

medium

A. Modifying subsets in place without copying causes all subsets to be identical

B. Extending result inside the loop causes infinite loop

C. Starting result with [[]] misses the empty subset

D. Using append instead of extend on subsets is incorrect

Solution

1. Step 1: Analyze subset modification

   The code appends num directly to subsets in result, modifying them in place.

2. Step 2: Consequence of in-place modification

   All subsets in result end up referencing the same list, causing duplicates and incorrect subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach copies subsets before adding new elements [OK]

Hint: Always copy subsets before adding new elements [OK]

Common Mistakes:

• Modifying lists in place
• Extending result inside loop without fix
• Wrong initial result value

4. Suppose the problem is modified so that puzzles can have repeated letters and words can be counted multiple times if they match multiple subsets of the puzzle letters. Which modification to the optimal bitmask + trie approach correctly handles this variant?

hard

A. Preprocess puzzles to remove duplicates and apply the original algorithm unchanged.

B. Modify dfs to not require the puzzle's first letter to be present in the word and allow counting multiple matches per word.

C. Enumerate all subsets of puzzle letters including duplicates and sum counts from trie traversal without filtering first letter.

D. Use a multiset trie that stores counts for repeated letters and traverse all subsets including duplicates.

Solution

1. Step 1: Understand variant requirements

   Repeated letters in puzzles and multiple counting per word require handling multisets, not just sets.

2. Step 2: Modify data structure and traversal

   A multiset trie that stores counts for repeated letters and traverses all subsets including duplicates correctly counts all matches.

3. Step 3: Why other options fail

   Ignoring first letter breaks mandatory condition; removing duplicates loses information; naive enumeration is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Multiset trie handles repeated letters and multiple counts correctly [OK]

Hint: Multiset trie needed for repeated letters and multiple counts [OK]

Common Mistakes:

• Ignoring repeated letters
• Removing duplicates incorrectly
• Dropping first letter condition

5. Suppose the problem is modified so that each element in the array can be used multiple times to form the k equal sum subsets (i.e., unlimited reuse of elements). Which modification to the backtracking with bitmask memoization approach is necessary to correctly solve this variant?

hard

A. Keep bitmask but allow resetting bits after each recursive call

B. Sort ascending instead of descending to handle reuse properly

C. Use the same code without changes because bitmask handles reuse implicitly

D. Remove bitmask usage since elements can be reused; track counts instead

Solution

1. Step 1: Understand reuse impact on state representation

   Bitmask tracks used elements uniquely; with reuse allowed, usage state is not binary but counts.

2. Step 2: Modify approach accordingly

   Bitmask must be removed or replaced by frequency counts to track how many times each element is used; otherwise, states are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask cannot represent multiple uses of same element [OK]

Hint: Bitmask tracks usage once; reuse breaks this assumption [OK]

Common Mistakes:

• Trying to reuse bitmask for multiple uses
• Ignoring state representation changes