Last updated on January 9th, 2025 at 03:30 am
Here, we see a Largest Divisible Subset LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, Math
Companies
Level of Question
Medium
Largest Divisible Subset LeetCode Solution
Table of Contents
1. Problem Statement
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, or
- answer[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]
2. Coding Pattern Used in Solution
The coding pattern used in this code is Dynamic Programming with Backtracking. This pattern involves solving a problem by breaking it into smaller subproblems (dynamic programming) and then reconstructing the solution (backtracking). Specifically, the code uses a Longest Increasing Subsequence (LIS)-like approach, where the condition for increasing is that one number must be divisible by another.
3. Code Implementation in Different Languages
3.1 Largest Divisible Subset C++
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int n=nums.size(), maxi=1, num=-1;
vector<int>v;
sort(nums.begin(), nums.end());
vector<int>dp(n, 1);
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(!(nums[i]%nums[j]) && dp[i]<dp[j]+1){
dp[i]=dp[j]+1;
if(maxi<dp[i]){
maxi=dp[i];
}
}
}
}
for(int i=n-1; i>=0; i--){
if(maxi==dp[i] && (num==-1 || !(num%nums[i]))){
v.push_back(nums[i]);
maxi--;
num=nums[i];
}
}
return v;
}
};
3.2 Largest Divisible Subset Java
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
Arrays.sort(nums);
int maxSize = 1, maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
}
}
}
}
List<Integer> result = new ArrayList<>();
int num = nums[maxIndex];
for (int i = maxIndex; i >= 0; i--) {
if (num % nums[i] == 0 && dp[i] == maxSize) {
result.add(nums[i]);
num = nums[i];
maxSize--;
}
}
return result;
}
}
3.3 Largest Divisible Subset JavaScript
var largestDivisibleSubset = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const dp = new Array(n).fill(1);
let maxSize = 1, maxIndex = 0;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] % nums[j] === 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
}
}
}
}
const result = [];
let num = nums[maxIndex];
for (let i = maxIndex; i >= 0; i--) {
if (num % nums[i] === 0 && dp[i] === maxSize) {
result.push(nums[i]);
num = nums[i];
maxSize--;
}
}
return result;
};
3.4 Largest Divisible Subset Python
class Solution(object):
def largestDivisibleSubset(self, nums):
nums.sort()
n = len(nums)
dp = [1] * n
max_size, max_index = 1, 0
for i in range(1, n):
for j in range(i):
if nums[i] % nums[j] == 0:
dp[i] = max(dp[i], dp[j] + 1)
if dp[i] > max_size:
max_size = dp[i]
max_index = i
result = []
num = nums[max_index]
for i in range(max_index, -1, -1):
if num % nums[i] == 0 and dp[i] == max_size:
result.append(nums[i])
num = nums[i]
max_size -= 1
return result
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n2) | O(n) |
| Java | O(n2) | O(n) |
| JavaScript | O(n2) | O(n) |
| Python | O(n2) | O(n) |
- The code uses Dynamic Programming with Backtracking to solve the problem.
- The time complexity is dominated by the nested loops, making it (O(n^2)).
- The space complexity is linear, (O(n)), due to the
dparray and result storage.