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.
Approach 01:
-
C++
-
Python
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int totalNums = nums.size();
sort(nums.begin(), nums.end());
vector<int> subsetLength(totalNums, 1); // Length of divisible subset ending at each index
vector<int> previousIndex(totalNums, -1); // To reconstruct the subset
vector<int> result;
int maxSubsetEndIndex = 0;
int maxSubsetLength = 1;
for (int i = 1; i < totalNums; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && subsetLength[i] < subsetLength[j] + 1) {
subsetLength[i] = subsetLength[j] + 1;
previousIndex[i] = j;
if (subsetLength[i] > maxSubsetLength) {
maxSubsetLength = subsetLength[i];
maxSubsetEndIndex = i;
}
}
}
}
// Reconstruct the subset
while (maxSubsetEndIndex != -1) {
result.push_back(nums[maxSubsetEndIndex]);
maxSubsetEndIndex = previousIndex[maxSubsetEndIndex];
}
return result;
}
};
from typing import List
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
totalNums = len(nums)
nums.sort()
subsetLength = [1] * totalNums # Length of divisible subset ending at each index
previousIndex = [-1] * totalNums # To reconstruct the subset
result = []
maxSubsetLength = 1
maxSubsetEndIndex = 0
for i in range(1, totalNums):
for j in range(i):
if nums[i] % nums[j] == 0 and subsetLength[i] < subsetLength[j] + 1:
subsetLength[i] = subsetLength[j] + 1
previousIndex[i] = j
if subsetLength[i] > maxSubsetLength:
maxSubsetLength = subsetLength[i]
maxSubsetEndIndex = i
# Reconstruct the subset
while maxSubsetEndIndex != -1:
result.append(nums[maxSubsetEndIndex])
maxSubsetEndIndex = previousIndex[maxSubsetEndIndex]
return result
Time Complexity:
- Sorting:
The input array is sorted at the beginning, which takes \( O(n \log n) \) time.
- Nested Loops:
For each pair \( (i, j) \), the algorithm checks divisibility and updates the DP arrays. This takes \( O(n^2) \) time.
- Reconstruction:
Reconstructing the subset involves at most \( O(n) \) steps.
- Total Time Complexity:
\( O(n^2) \)
Space Complexity:
- DP Arrays:
Two arrays of size \( n \): one for storing the length of the subset and one for previous indices. This gives \( O(n) \) space.
- Output Vector:
The result vector storing the largest divisible subset also takes \( O(n) \) space in the worst case.
- Total Space Complexity:
\( O(n) \)