Algorithm
Problem Name: 368. Largest Divisible Subset
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, oranswer[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 <= 10001 <= nums[i] <= 2 * 109- All the integers in
numsare unique.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const largestDivisibleSubset = function(nums) {
const n = nums.length;
if(n === 0 || n === 1) return nums
let maxSize = 0;
const dp = Array(n).fill(1)
nums.sort((a, b) => a - b)
for(let i = 1; i < n; i++> {
for(let j = i - 1; j >= 0; j--) {
if(nums[i] % nums[j] === 0) {
const tmp = dp[j] + 1
if(tmp > dp[i]) dp[i] = tmp
}
}
if(dp[i] > maxSize) maxSize = dp[i]
}
const res = []
let pivot = 0
for(let i = n - 1; i >= 0; i--) {
if(dp[i] === maxSize && (pivot % nums[i] === 0)) {
pivot = nums[i]
maxSize--
res.push(nums[i])
}
}
return res
};
Input
nums = [1,2,3]
Output
[1,2]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def largestDivisibleSubset(self, nums):
dp, n = [[num] for num in sorted(nums)], len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
if not dp[j][-1] % dp[i][-1] and len(dp[i]) >= len(dp[j]):
dp[j] = dp[i] + dp[j][-1:]
return dp and sorted(dp, key = len)[-1]
Input
nums = [1,2,3]
Output
[1,2]
#3 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0368_LargestDivisibleSubset
{
public IList < int> LargestDivisibleSubset(int[] nums)
{
var n = nums.Length;
if (n <= 0) return nums;
Array.Sort(nums);
var length = new int[n];
var prevIndex = new int[n];
for (int i = 0; i < n; i++)
{
length[i] = 1;
prevIndex[i] = -1;
for (int j = 0; j < i; j++)
{
if (nums[i] % nums[j] == 0)
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
prevIndex[i] = j;
}
}
}
}
var maxDistance = 0;
var index = -1;
for (int i = 0; i < n; i++)
{
if (length[i] > maxDistance)
{
maxDistance = length[i];
index = i;
}
}
var result = new List < int>();
while (index != -1)
{
result.Add(nums[index]);
index = prevIndex[index];
}
return result;
}
}
}
Input
nums = [1,2,4,8]
Output
[1,2,4,8]