Dare2Solve
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.
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.
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.
O(n), to store the subsets for each number in the cache.
class Solution {
public:
std::vector<int> largestDivisibleSubset(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::unordered_map<int, std::vector<int>> cache;
std::vector<int> longest;
for (int i = 0; i < nums.size(); i++) {
int curr = nums[i];
std::vector<int> arr = {curr};
for (int j = 0; j < i; j++) {
std::vector<int> 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<int>(longest.begin() + 1, longest.end());
}
};
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:]
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
Map<Integer, List<Integer>> cache = new HashMap<>();
List<Integer> longest = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
List<Integer> arr = new ArrayList<>(Arrays.asList(curr));
for (int j = 0; j < i; j++) {
List<Integer> 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());
}
}
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);
};