Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0 must hold. Multiple maximum-length subsets may exist, and any valid maximum subset is accepted.
Example 1
Input: nums = [1, 16, 7, 8, 4]
Output: [1, 4, 8, 16]
Explanation: Every pair inside [1, 4, 8, 16] satisfies the divisibility rule. The value 7 cannot join the chain because no other chain value divides 7, apart from 1.
Example 2
Input: nums = [5, 7, 11]
Output: [5]
Explanation: No array value divides another array value, so every single-value subset has maximum length 1. The subsets [7] and [11] are equally valid.
Approach
Sorting places every possible divisor before a larger multiple. A valid chain can then grow from a smaller value toward a larger value. Divisibility is transitive: after a divides b and b divides c, a also divides c. Checking a new value against the previous chain endpoint therefore preserves the rule for every earlier chain value.
An array named dp stores the longest divisible-chain length ending at each sorted position. A second array named parent stores the chosen preceding position. Following parent links from the best ending position collects one maximum chain backward, and reversal restores ascending order.
Algorithm
Begin by sorting
numsin ascending order, because every possible divisor must appear before a larger multiple during chain construction.Give every
dpposition the value1and everyparentposition a self-link, because each number forms a valid one-value chain and needs a clear reconstruction endpoint.Process sorted positions from left to right, so every candidate predecessor already has a completed best chain length.
Compare the current value with every earlier value, and allow an extension only when the earlier value divides the current value so every extended chain preserves pairwise divisibility.
Replace
dp[current]andparent[current]after a strict length improvement, because only a longer predecessor chain provides a better answer ending at the current value.Track the position containing the largest
dpvalue, so reconstruction begins at the final value of a maximum divisible chain.Follow
parentlinks into an answer list and reverse the collected values, because predecessor traversal visits the selected chain from largest value to smallest value.
Dry Run
Largest Divisible Subset
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return one maximum divisible subset. vector<int> largestDivisibleSubset(vector<int>& nums) { int n = nums.size(); // Empty input has no valid subset. if (n == 0) { return {}; } // Put every divisor before a larger multiple. sort(nums.begin(), nums.end()); // Give every value a valid one-value chain. vector<int> dp(n, 1); // Store the chosen predecessor for each value. vector<int> parent(n); // Preserve the end of the longest chain. int bestEnd = 0; // Build lengths after all earlier states exist. for (int current = 0; current < n; current++) { // Mark a one-value chain as a stopping point. parent[current] = current; // Test every possible earlier divisor. for (int previous = 0; previous < current; previous++) { bool divisible = nums[current] % nums[previous] == 0; bool longer = dp[previous] + 1 > dp[current]; // Extend only through a better divisible chain. if (divisible && longer) { // Save the improved chain length. dp[current] = dp[previous] + 1; // Remember the predecessor giving improvement. parent[current] = previous; } } // Move the endpoint only after a longer chain. if (dp[current] > dp[bestEnd]) { bestEnd = current; } } // Collect values while following parent links. vector<int> answer; // Stop at the self-linked chain beginning. while (parent[bestEnd] != bestEnd) { answer.push_back(nums[bestEnd]); bestEnd = parent[bestEnd]; } // Add the smallest selected value. answer.push_back(nums[bestEnd]); // Restore ascending divisor-to-multiple order. reverse(answer.begin(), answer.end()); return answer; }};// Driver codeint main() { vector<int> nums = {1, 16, 7, 8, 4}; Solution obj; vector<int> answer = obj.largestDivisibleSubset(nums); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the number of elements, because sorting costs O(N log N) and the nested comparison loops cost O(N2). The quadratic term dominates the total cost.
Space Complexity: O(N), because the dp, parent, and reconstructed answer arrays each store at most N values.
Interview follow-up Questions
Sorting places every smaller divisor before a larger multiple. Each current value can then extend only completed chains from earlier positions.
Be the first to add a comment.