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. Consider the following Python code implementing letter case permutation using backtracking with in-place modification. What is the final output when the input string is "a1b"?

from typing import List

def letterCasePermutation(s: str) -> List[str]:
    res = []
    arr = list(s)
    def backtrack(i: int):
        if i == len(arr):
            res.append(''.join(arr))
            return
        if arr[i].isdigit():
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()
            backtrack(i + 1)
            arr[i] = arr[i].upper()
            backtrack(i + 1)
            arr[i] = s[i]  # revert to original
    backtrack(0)
    return res

print(letterCasePermutation("a1b"))

easy

A. ['a1b', 'a1B', 'A1B', 'A1b']

B. ['a1b', 'A1b', 'a1B', 'A1B']

C. ['a1b', 'a1B', 'A1b', 'A1B']

D. ['A1b', 'a1b', 'A1B', 'a1B']

Solution

1. Step 1: Trace backtrack calls for input "a1b"

   Index 0 is 'a' (letter), toggled to 'a' then 'A'. Index 1 is '1' (digit), skipped. Index 2 is 'b' (letter), toggled to 'b' then 'B'.

2. Step 2: Collect permutations in order

   Order of appending: 'a1b', 'a1B', 'A1b', 'A1B'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected toggling order [OK]

Hint: Digits skip toggling; letters toggle lower then upper [OK]

Common Mistakes:

• Swapping order of uppercase/lowercase calls
• Misplacing digit handling

2. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?

easy

A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.

B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.

C. Dynamic programming based on subset sums without pruning or memoization.

D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.

Solution

1. Step 1: Understand problem constraints

   The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.

2. Step 2: Identify suitable algorithm

   Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + memoization prunes repeated states [OK]

Hint: Bitmask + memoization prunes repeated states [OK]

Common Mistakes:

• Assuming greedy always works for partitioning
• Confusing DP without pruning as efficient
• Ignoring memoization benefits

3. You need to generate all possible subsets of a given set of distinct integers. Which approach guarantees generating every subset exactly once with a time complexity proportional to the number of subsets times the size of each subset?

easy

A. Greedy algorithm that picks elements based on their value order

B. Enumerate all bitmasks from 0 to 2^n - 1, selecting elements where bits are set

C. Dynamic programming to count subsets without generating them

D. Sorting the array and using two pointers to find pairs

Solution

1. Step 1: Understand the problem

   We want to generate all subsets of a set, which are 2^n in number.

2. Step 2: Identify the approach that enumerates all subsets

   Bitmask enumeration from 0 to 2^n - 1 maps each bit to an element's inclusion, guaranteeing all subsets exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets systematically [OK]

Hint: Bitmask from 0 to 2^n-1 enumerates all subsets [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all subsets efficiently

4. What is the time complexity of the bitmask enumeration approach for counting the number of max bitwise-OR subsets in an array of length n?

medium

A. O(n^2)

B. O(n!)

C. O(2^n)

D. O(n * 2^n)

Solution

1. Step 1: Identify outer loop over all subsets

   There are 2^n subsets, so outer loop runs 2^n times.

2. Step 2: Identify inner loop over elements for each subset

   For each subset, we check up to n elements to compute OR, so inner loop is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   2^n subsets x n elements per subset -> O(n * 2^n) [OK]

Hint: Each subset requires checking n elements -> O(n * 2^n) [OK]

Common Mistakes:

• Confusing 2^n subsets with O(2^n) ignoring inner loop
• Assuming quadratic or factorial complexity

5. Suppose the problem is modified so that elements can be chosen multiple times (unlimited reuse) to form subsets. Which approach correctly adapts to count the number of max bitwise-OR subsets under this new constraint?

hard

A. Use dynamic programming over OR values with state compression to count combinations

B. Use backtracking with memoization to handle repeated elements and prune search

C. Use the same bitmask enumeration approach since subsets remain finite

D. Sort elements and greedily pick those with highest bits until max OR is reached

Solution

1. Step 1: Recognize infinite subsets due to unlimited reuse

   Bitmask enumeration is infeasible as subsets are infinite with reuse allowed.

2. Step 2: Use DP over OR states to count combinations efficiently

   DP with state compression tracks counts of subsets achieving each OR value, handling reuse.

3. Step 3: Understand greedy or naive backtracking fail due to infinite or redundant subsets

   Greedy misses combinations; naive backtracking is exponential and inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP over OR states handles reuse -> correct and efficient [OK]

Hint: Reuse means infinite subsets -> DP over OR states needed [OK]

Common Mistakes:

• Trying bitmask enumeration despite infinite subsets
• Using greedy approach ignoring subset counts