algoadvance

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj == 0 or Sj % Si == 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: [1,2,3]
Output: [1,2] (or [1,3])

Example 2:

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

Clarifying Questions

  1. Q: Can the input array be empty?
    A: No, the input array will have at least one element.

  2. Q: Can input arrays have very large numbers?
    A: Yes, but you can assume that computations will not cause integer overflow.

  3. Q: Are duplicate numbers allowed in the input array?
    A: No, the input array consists of distinct positive integers.

Strategy

  1. Sort the Array: Start by sorting the array. This helps in ensuring that for any pair Si and Sj with i < j, Si is guaranteed to be less than or equal to Sj.

  2. Dynamic Programming Approach:
    • Maintain a list dp where dp[i] stores the largest divisible subset that ends with the element nums[i].
    • For each nums[i], check all previous elements nums[j] (where j < i). If nums[i] % nums[j] == 0, then nums[i] can extend the subset ending with nums[j].
  3. Backtracking to Find Solution Path:
    • Use another list previous_index to help trace back the largest divisible subset.
    • previous_index[i] stores the index of the previous element in the divisible subset for nums[i].
  4. Extract the Longest Subset:
    • Once the dp and previous_index lists are prepared, determine the subset by backtracking from the maximum subset length found.

Code Implementation

def largestDivisibleSubset(nums):
    if not nums:
        return []
    
    nums.sort()
    n = len(nums)
    
    dp = [[num] for num in nums]
    max_subset = []
    
    for i in range(n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and len(dp[j]) + 1 > len(dp[i]):
                dp[i] = dp[j] + [nums[i]]
        if len(dp[i]) > len(max_subset):
            max_subset = dp[i]
    
    return max_subset

Time Complexity

Overall Time Complexity: O(n^2)

This should be manageable for standard input limits in coding interviews.

Try our interview co-pilot at AlgoAdvance.com