Scale Engineer

Largest Divisible Subset

Med
#0355Time: O(2^N * N^2). There are `2^N` subsets. For each subset of size `K`, the validation check takes `O(K^2)` pairwise comparisons. The average subset size is `N/2`, leading to this complexity.Space: O(N). The space is required to store the `currentSubset` and the `largestSubset` found. Each can have a maximum size of `N`.
Patterns
MathDynamic Programming
Algorithms
Sorting
Data structures
Array

Prompt

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

  • answer[i] % answer[j] == 0, or
  • answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

 

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2 * 109
  • All the integers in nums are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This naive approach involves generating every possible subset of the input array nums. For each subset, we check if it satisfies the divisible subset property, where for any pair of elements, one must divide the other. We keep track of the largest valid subset found.

Algorithm

  • Initialize an empty list largestSubset to store the result.
  • Let N be the number of elements in nums.
  • Loop through all integers from 0 to 2^N - 1. Each integer i acts as a bitmask.
  • For each i, create a currentSubset:
    • Iterate from j = 0 to N-1.
    • If the j-th bit of i is set, add nums[j] to currentSubset.
  • Check if currentSubset is a valid divisible subset:
    • Assume it's valid (isValid = true).
    • Iterate through all pairs of elements (a, b) in currentSubset.
    • If a % b != 0 and b % a != 0, set isValid = false and break the loops.
  • If isValid is true and currentSubset.size() > largestSubset.size(), update largestSubset = currentSubset.
  • After checking all 2^N possibilities, return largestSubset.

Walkthrough

The core idea is to explore the entire solution space. The number of subsets of a set with N elements is 2^N. We can represent each subset using a bitmask of length N. For each bitmask, we construct the corresponding subset. Then, we perform a validation check on this subset. The validation involves iterating through all pairs of numbers in the subset and checking the divisibility condition. If a subset is valid, we compare its size with the largest one found so far and update if necessary. While simple to conceptualize, this method is computationally expensive and impractical for the given constraints.

Complexity

Time

O(2^N * N^2). There are `2^N` subsets. For each subset of size `K`, the validation check takes `O(K^2)` pairwise comparisons. The average subset size is `N/2`, leading to this complexity.

Space

O(N). The space is required to store the `currentSubset` and the `largestSubset` found. Each can have a maximum size of `N`.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

Cons

  • Extremely inefficient.

  • Feasible only for very small N (e.g., N < 20).

  • Will result in a 'Time Limit Exceeded' error for the given problem constraints.

Solutions

class Solution { public List < Integer > largestDivisibleSubset ( int [] nums ) { Arrays . sort ( nums ); int n = nums . length ; int [] f = new int [ n ]; Arrays . fill ( f , 1 ); int k = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < i ; ++ j ) { if ( nums [ i ] % nums [ j ] == 0 ) { f [ i ] = Math . max ( f [ i ], f [ j ] + 1 ); } } if ( f [ k ] < f [ i ]) { k = i ; } } int m = f [ k ]; List < Integer > ans = new ArrayList <>(); for ( int i = k ; m > 0 ; -- i ) { if ( nums [ k ] % nums [ i ] == 0 && f [ i ] == m ) { ans . add ( nums [ i ]); k = i ; -- m ; } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem