Largest Divisible Subset

Problem Statement

Given a collection of distinct positive integers named nums, the task is to identify and return the largest subset called answer. This subset should have the special property that every pair (answer[i], answer[j]) within it complies with either of the conditions:

• answer[i] % answer[j] == 0 (i.e., answer[i] is divisible by answer[j])
• answer[j] % answer[i] == 0 (i.e., answer[j] is divisible by answer[i])

The challenge is to ensure that every possible pair within the subset satisfies one of these divisibility conditions. If there are multiple valid subsets which can be considered as the largest, any one of these valid subsets can be returned.

Examples

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.

Approach and Intuition

• Sorting the Array:
  Start by sorting the array nums. Sorting helps in a way that if a number a divides another number b and if a < b, then in a sorted array, a will always come before b. This property is crucial to solving the problem efficiently using dynamic programming.

• Using Dynamic Programming to Construct the Subset:
  Use a dynamic programming approach where dp[i] represents the largest divisible subset that ends with the element at index i in the sorted array.

1. Initialize the dp[i] array where each dp[i] is initially the subset {nums[i]} itself, as every number is divisible by itself.
2. For each element at index i, look for previous elements at index j (where j < i). Check if nums[i] % nums[j] == 0. If true, it means the subset ending at j can be extended by nums[i].
3. Update dp[i] to be the union of dp[i] and dp[j] if this union results in a larger subset.
4. Keep track of the size of the largest subset formed and maintain this subset.

• Retrieving the Result:
  After populating the dp array, the largest subset would be the one with the maximum size among all dp[i] subsets. Retrieve this subset.

• Efficiency:
  The efficiency of this method comes from avoiding the need to check each subset explicitly, reducing what could be a potentially exponential time complexity problem to a more manageable polynomial complexity. Sorting the array nums takes O(N log N), and the double-loop for filling dp array takes O(N^2). Thus, the overall time complexity is O(N^2 + N log N).

• Edge Cases:
  Since the numbers are unique and the range of possible values for the numbers is quite large, care must be taken to handle small arrays or arrays where no two numbers are divisible efficiently.

This approach ensures we find a valid subset satisfying the given conditions in an optimized manner, utilizing sorting and dynamic programming.

Solutions

class Solution {
  HashMap<Integer, List<Integer>> subsetMap = new HashMap<>();
  int[] elements = {};

  private List<Integer> findDivisibleSubsets(Integer index) {
    if (subsetMap.containsKey(index)) return subsetMap.get(index);
    
    List<Integer> largestSubset = new ArrayList<>();
    for (int prevIndex = 0; prevIndex < index; ++prevIndex) {
      if (elements[index] % elements[prevIndex] == 0) {
        List<Integer> currentSubset = findDivisibleSubsets(prevIndex);
        if (largestSubset.size() < currentSubset.size()) largestSubset = currentSubset;
      }    
    }
    
    List<Integer> extendedSubset = new ArrayList<>(largestSubset);
    extendedSubset.add(elements[index]);

    subsetMap.put(index, extendedSubset);
    return extendedSubset;
  }

  public List<Integer> largestDivisibleSubset(int[] nums) {
    int size = nums.length;
    if (size == 0) return new ArrayList<>();
    
    subsetMap.clear();
    Arrays.sort(nums);
    elements = nums;
    
    List<Integer> finalSubset = new ArrayList<>();
    for (int i = 0; i < size; ++i) {
      List<Integer> currentSubset = findDivisibleSubsets(i);
      if (finalSubset.size() < currentSubset.size()) finalSubset = currentSubset;
    }

    return finalSubset;
  }
}