Missing test case "368. Largest Divisible Subset"


  • 0
    X

    [3 4 16 8]
    in this case, the smallest number 3 is not in the result list [4 16 8]


  • 0

    The answer for [3, 4, 6, 8] is either [3, 6] or [4, 8]. What do you mean?


  • 0
    X

    @1337c0d3r
    Sorry, it's typo. [3 4 8 16], or [3 4 16 8].
    This code is correct.

    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            int n = nums.size();
            if (n <= 1) {
                return nums;
            }
            vector<int> sum(n, 0);
            vector<int> best;
            int maxL = 0;
            sort(nums.begin(), nums.end());
            for (int i = n - 2; i >= 0; i--) {
                for (int j = i + 1; j < n; j++) {
                    if (!(nums[j] % nums[i])) {
                        sum[i] = max(sum[i], sum[j] + 1);
                        maxL = max(maxL, sum[i]);
                    }
                }
            }
            int i = 0; 
            while (maxL >= 0) {
                if (sum[i] == maxL) {
                    best.push_back(nums[i]);
                    maxL--;
                    int j = i;
                    while (++j < n && (nums[j] % nums[i] || sum[j] != maxL)) ;
                    i = j;
                } else {
                    i++;
                }
            }
            return best;
        }
    };
    

    while this one is wrong, because it cannot pass the case I listed, but it can be accepted.

    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            int n = nums.size();
            if (n <= 1) {
                return nums;
            }
            vector<int> sum(n, 0);
            vector<int> best;
            int maxL = 0;
            sort(nums.begin(), nums.end());
            for (int i = n - 2; i >= 0; i--) {
                for (int j = i + 1; j < n; j++) {
                    if (!(nums[j] % nums[i])) {
                        sum[i] = max(sum[i], sum[j] + 1);
                        maxL = max(maxL, sum[i]);
                    }
                }
            }
            int i = 0; 
            while (maxL >= 0) {
                if (sum[i] == maxL) {
                    best.push_back(nums[i]);
                    maxL--;
                    int j = i;
                    while (++j < n && (nums[j] % nums[i] || sum[j] != maxL)) ;
                    i = j;
                }
            }
            return best;
        }
    };
    

  • 0

    @xiedwill said in Missing test case "368. Largest Divisible Subset":

    [3 4 16 8]

    Got it. I have just added this test case.

    Thanks for making LeetCode better. :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.