🎨Now live: Try our Free AI Image Generation Feature

Description
The problem requires finding the largest subset of numbers from a given array such that for any two elements in the subset, one divides the other perfectly. The result should be the largest such subset in terms of size.
Intuition
The main observation here is that the problem relates to divisibility. Sorting the array will help ensure that for any number at index i
, the elements before it can be potential divisors, and we can build the subset progressively.
Approach
- Sorting: First, we sort the array to handle numbers from smallest to largest.
- Dynamic Programming Approach: We use a cache (or dictionary) to store the largest divisible subset for each number encountered so far.
- Subset Construction: For each number, we check every number before it and determine if it divides the current number. If it does, and the subset formed by including the current number is larger, we update the subset.
- Return the Largest Subset: At the end of the iteration, we return the largest subset found, excluding the first element.
Complexity
Time Complexity:
O(n^2), where n
is the size of the input array. We iterate over each element and for each element, we check every previous element.
Space Complexity:
O(n), to store the subsets for each number in the cache.
Code
C++
class Solution {
public:
std::vector largestDivisibleSubset(std::vector& nums) {
std::sort(nums.begin(), nums.end());
std::unordered_map> cache;
std::vector longest;
for (int i = 0; i < nums.size(); i++) {
int curr = nums[i];
std::vector arr = {curr};
for (int j = 0; j < i; j++) {
std::vector prevArray = cache[nums[j]];
if (curr % prevArray.back() == 0 && prevArray.size() > arr.size()) {
arr = prevArray;
}
}
arr.push_back(curr);
if (arr.size() > longest.size()) {
longest = arr;
}
cache[curr] = arr;
}
return std::vector(longest.begin() + 1, longest.end());
}
};
Python
class Solution:
def largestDivisibleSubset(self, nums):
nums.sort()
cache = {}
longest = []
for i in range(len(nums)):
curr = nums[i]
arr = [curr]
for j in range(i):
prev_array = cache[nums[j]]
if curr % prev_array[-1] == 0 and len(prev_array) > len(arr):
arr = prev_array[:]
arr.append(curr)
if len(arr) > len(longest):
longest = arr
cache[curr] = arr
return longest[1:]
Java
class Solution {
public List largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
Map> cache = new HashMap<>();
List longest = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
List arr = new ArrayList<>(Arrays.asList(curr));
for (int j = 0; j < i; j++) {
List prevArray = cache.get(nums[j]);
if (curr % prevArray.get(prevArray.size() - 1) == 0 && prevArray.size() > arr.size()) {
arr = new ArrayList<>(prevArray);
}
}
arr.add(curr);
if (arr.size() > longest.size()) {
longest = arr;
}
cache.put(curr, arr);
}
return longest.subList(1, longest.size());
}
}
JavaScript
var largestDivisibleSubset = function (nums) {
nums.sort((a, b) => a - b);
let cache = {};
let largest = 0;
let longest = [];
for (let i = 0; i < nums.length; i++) {
let curr = nums[i];
let arr = [curr];
for (let j = 0; j < i; j++) {
let prevArray = cache[nums[j]];
if (curr % prevArray[prevArray.length - 1] === 0 && prevArray.length > arr.length) {
arr = prevArray//.concat(curr);
}
}
//if(arr[0]!==curr)
arr = arr.concat(curr);
if (arr.length > longest.length) {
longest = arr;
}
cache[curr] = arr;
}
//console.log(cache)
return longest.slice(1);
};