Description
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
nums are unique.
Solutions
Solution 1
PythonJavaC++GoTypeScriptRust
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums)
f = [1] * n
k = 0
for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0:
f[i] = max(f[i], f[j] + 1)
if f[k] < f[i]:
k = i
m = f[k]
i = k
ans = []
while m:
if nums[k] % nums[i] == 0 and f[i] == m:
ans.append(nums[i])
k, m = i, m - 1
i -= 1
return ans(code-box)
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] f = new int[n];
Arrays.fill(f, 1);
int k = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
if (f[k] < f[i]) {
k = i;
}
}
int m = f[k];
List<Integer> ans = new ArrayList<>();
for (int i = k; m > 0; --i) {
if (nums[k] % nums[i] == 0 && f[i] == m) {
ans.add(nums[i]);
k = i;
--m;
}
}
return ans;
}
}(code-box)
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
ranges::sort(nums);
int n = nums.size();
int f[n];
int k = 0;
for (int i = 0; i < n; ++i) {
f[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0) {
f[i] = max(f[i], f[j] + 1);
}
}
if (f[k] < f[i]) {
k = i;
}
}
int m = f[k];
vector<int> ans;
for (int i = k; m > 0; --i) {
if (nums[k] % nums[i] == 0 && f[i] == m) {
ans.push_back(nums[i]);
k = i;
--m;
}
}
return ans;
}
};(code-box)
func largestDivisibleSubset(nums []int) (ans []int) {
sort.Ints(nums)
n := len(nums)
f := make([]int, n)
k := 0
for i := 0; i < n; i++ {
f[i] = 1
for j := 0; j < i; j++ {
if nums[i]%nums[j] == 0 {
f[i] = max(f[i], f[j]+1)
}
}
if f[k] < f[i] {
k = i
}
}
m := f[k]
for i := k; m > 0; i-- {
if nums[k]%nums[i] == 0 && f[i] == m {
ans = append(ans, nums[i])
k = i
m--
}
}
return
}(code-box)
function largestDivisibleSubset(nums: number[]): number[] {
nums.sort((a, b) => a - b);
const n = nums.length;
const f: number[] = Array(n).fill(1);
let k = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[i] % nums[j] === 0) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
if (f[k] < f[i]) {
k = i;
}
}
let m = f[k];
const ans: number[] = [];
for (let i = k; m > 0; --i) {
if (nums[k] % nums[i] === 0 && f[i] === m) {
ans.push(nums[i]);
k = i;
--m;
}
}
return ans;
}(code-box)
impl Solution {
pub fn largest_divisible_subset(nums: Vec<i32>) -> Vec<i32> {
let mut nums = nums;
nums.sort();
let n = nums.len();
let mut f = vec![1; n];
let mut k = 0;
for i in 0..n {
for j in 0..i {
if nums[i] % nums[j] == 0 {
f[i] = f[i].max(f[j] + 1);
}
}
if f[k] < f[i] {
k = i;
}
}
let mut m = f[k];
let mut ans = Vec::new();
for i in (0..=k).rev() {
if nums[k] % nums[i] == 0 && f[i] == m {
ans.push(nums[i]);
k = i;
m -= 1;
}
}
ans
}
}(code-box)
