6ms C++ beats 100% w/ explanations


  • 4

    Solution #1 (TLE)
    This solution builds upon the naive approach of building up a solution by either adding an element to the solution (if it passes the divisibility check) or by skipping the value as all nums are iterated over. Nums is first sorted so that it is easier to test if a new (larger) num satisfies the divisibility check of the current solution by only checking the last element of the solution (others, like @StefanPochmann, have talked about this). Speed is O(2^n), and Space is O(n).

    class Solution {
        int bSz=0, sPos=0, nSz;
        vector<int> nums, sol, best=vector<int>(0);
        
        int passes(int v, int i) {
            return ( (sPos==0) || ((v%sol[sPos-1])==0) );
        }
        void rec(int i) {
            for ( ; i<nSz; ++i ) {
                if ( passes(nums[i],i) ) {
                    sol[sPos++]=nums[i];
                    rec(i+1);   // w/ num[i] in solution
                    --sPos;
                }               // else, w/o num[i] in solution
            }
            if ( bSz < sPos ) {
                bSz = sPos;     // store best
                best = vector<int>(sol.begin(), sol.begin()+sPos);
            }
        }
    public:
        vector<int> largestDivisibleSubset(vector<int>& numsOrig) {
            if ( (nSz=numsOrig.size())<=1 ) return numsOrig; 
            nums = numsOrig;
            sol = vector<int>(nSz);
            //
            sort (nums.begin(), nums.end());
            //
            rec(0);
            return best;
        }
    };
    

    Solution #2 (Accepted 149ms)
    Like Dijkstra's shortest path algorithm, it can be observed that a num should only be considered if it contributes to a better solution (in this case a longer subset). Therefore the distance of a num contributing to any partial solution can be recorded in a 'furthest' vector (where it is found in the solution), of size n, and only be considered again if it has a further solution position.
    // don't consider the num 32 in a solution of [1,32,...] when a better solution [1,2,4,32,...] has already been found
    Someone can correct me if I am wrong, but I believe the Speed is O(n^2) and the Space is still O(n). The reason it is no longer O(2^n) is because the the outer loop runs in O(n) while the inner recursive loop now only expands ~once per new divisible num, also O(n). In other words, the recursive portion is like a DFS that walks the remaining nodes once; then, later attempts to visit the same node are rejected for not having a further solution position.

    class Solution {
        int bSz=0, sPos=0, nSz;
        vector<int> nums, sol, furthest, best=vector<int>(0);
        
        int passes(int v, int i) {
            if ( sPos==0 ) return 1;
            if ( (sPos>furthest[i]) && ((v%sol[sPos-1])==0) ) {
                furthest[i]=sPos;
                return 1;       // mark the position
            }
            return 0;
        }
        void rec(int i) {
            for ( ; i<nSz; ++i ) {
                if ( passes(nums[i],i) ) {
                    sol[sPos++]=nums[i];
                    rec(i+1);   // w/ num[i] in solution
                    --sPos;
                }               // else, w/o num[i] in solution
            }
            if ( bSz < sPos ) {
                bSz = sPos;     // store best
                best = vector<int>(sol.begin(), sol.begin()+sPos);
            }
        }
    public:
        vector<int> largestDivisibleSubset(vector<int>& numsOrig) {
            if ( (nSz=numsOrig.size())<=1 ) return numsOrig; 
            nums = numsOrig;
            sol = vector<int>(nSz);
            furthest = vector<int>(nSz,0);
            //
            sort (nums.begin(), nums.end());
            //
            rec(0);
            return best;
        }
    };
    

    Solution #3 (Accepted 6ms)
    Additional pruning can be added for early rejection of numbers that will not contribute to a better solution than what has already been found, with the below check:
    // given input [1...1000] and a current best solution of [1,2,4,8...512], don't proceed with a solution like [1,3,99] or [1,400] because the optimal way to expand these solutions would be to multiply the last number by 2 repeatedly, but a larger best-subset would require a final number > 1000.
    So a check is added to our iterative loop to see if there remains a large enough num to satisfy this constraint with: largest > num * 2^(difference in solution size to the best known solution size). This check requires O(1) additional complexity leaving the Speed at O(n^2) and the Space O(n).

    class Solution {
        int bSz=0, sPos=0, nSz, largest;
        vector<int> nums, sol, furthest, best=vector<int>(0);
        
        int passes(int v, int i) {
            if ( sPos==0 ) return 1;
            if ( (sPos>furthest[i]) && ((v%sol[sPos-1])==0) ) {
                furthest[i]=sPos;
                return 1;       // mark the position
            }
            return 0;
        }
        void rec(int i) {
            for ( ; i<nSz; ++i ) {
                if ( bSz>sPos && ((((long)1)<<(bSz-sPos))*nums[i])>largest ) break;
                if ( passes(nums[i],i) ) {
                    sol[sPos++]=nums[i];
                    rec(i+1);   // w/ num[i] in solution
                    --sPos;
                }               // else, w/o num[i] in solution
            }
            if ( bSz < sPos ) {
                bSz = sPos;     // store best
                best = vector<int>(sol.begin(), sol.begin()+sPos);
            }
        }
    public:
        vector<int> largestDivisibleSubset(vector<int>& numsOrig) {
            if ( (nSz=numsOrig.size())<=1 ) return numsOrig; 
            nums = numsOrig;
            sol = vector<int>(nSz);
            furthest = vector<int>(nSz,0);
            //
            sort (nums.begin(), nums.end());
            largest = nums.back();
            //
            rec(0);
            return best;
        }
    };
    

  • 0

    C Solution (port) (Accepted 3ms):

    int sPos=0, *sol=0, *best=0, *furthest=0, largest=0, *nums=0, nSz=0, *bSz=0;
    int asc(const void *a, const void *b) { return ( *(int*)a - *(int*)b ); }
    
    int passes(int v, int i) {
        if ( sPos==0 ) return 1;
        if ( (sPos>furthest[i]) && ((v%sol[sPos-1])==0) ) {
            furthest[i]=sPos;
            return 1;
        }
        return 0;
    }
    void rec(int i) {
        for ( ; i<nSz; ++i ) {
            if ( (*bSz)>sPos && ((((long)1)<<((*bSz)-sPos))*nums[i])>largest ) break;
            if ( passes(nums[i],i) ) {
                sol[sPos++]=nums[i];
                rec(i+1);   // w/
                --sPos;
            }               // w/o
        }
        if ( (*bSz) < sPos ) {
            best = realloc(best, sizeof(int)*((*bSz)=sPos));
            memcpy(best,sol,sizeof(int)*sPos);
        }
    }
    int* largestDivisibleSubset(int* numsOrig, int numsSize, int* returnSize) {
        nums=numsOrig;
        nSz=numsSize;
        bSz=returnSize; (*bSz) = 0;
        best=sPos=0; 
        sol = malloc(sizeof(int)*nSz);
        furthest = calloc(nSz, sizeof(int));
        qsort(nums, nSz, sizeof(int), asc);
        largest = nums[nSz-1];
        rec(0);
        free(sol); free(furthest);
        return best;
    }
    

  • 0

    JavaScript Solution (port) (Accepted 95ms):

    var largestDivisibleSubset = function(nums) {
        var sPos=0, sol=[], best=[], end=nums.length, furthest=[], largest;
        nums.sort(asc);
        largest = nums[end-1];
        rec(0);
        return best;
        
        function rec(i) {
            for ( ; i<end; ++i ) {
                if ( best.length>sPos && ((1<<(best.length-sPos))*nums[i])>largest ) break;
                if ( passes(i) ) {
                    sol[sPos++]=nums[i];
                    rec(i+1);   // w/
                    --sPos;
                }               // w/o
            }
            if ( best.length<sPos ) best=sol.slice(0,sPos);
        }
        function passes(i) {
            if ( (furthest[i]==void 0 || sPos>furthest[i]) && 
               ( sPos==0 || (nums[i]%sol[sPos-1])==0 ) ) {
                furthest[i]=sPos;
                return 1;       // mark the position
            }
            return 0;
        }
    };
    function asc(a,b) { return a-b; } 
    

  • 0

    awesome !!!
    It would be better with good explanation.


  • 0
    F

    The 6ms pruning is great. Pruning strategy is always like art.


  • 0
    C
    This post is deleted!

Log in to reply
 

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