4 lines in Python


  • 69
    def largestDivisibleSubset(self, nums):
        S = {-1: set()}
        for x in sorted(nums):
            S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
        return list(max(S.values(), key=len))
    

    My S[x] is the largest subset with x as the largest element, i.e., the subset of all divisors of x in the input. With S[-1] = emptyset as useful base case. Since divisibility is transitive, a multiple x of some divisor d is also a multiple of all elements in S[d], so it's not necessary to explicitly test divisibility of x by all elements in S[d]. Testing x % d suffices.

    While storing entire subsets isn't super efficient, it's also not that bad. To extend a subset, the new element must be divisible by all elements in it, meaning it must be at least twice as large as the largest element in it. So with the 31-bit integers we have here, the largest possible set has size 31 (containing all powers of 2).


  • 4

    As usual you're amazing


  • 0
    T

    Great solution. About the base case, I think we can simply use 1 instead of -1.


  • 0

    @StefanPochmann Amazing~~~! btw, can anyone tell me how to find all my bookmarks in this new version of discussion :P


  • 2

    @MingHan1990 Go to your profile page, click the vertical-three-dots button, then on bookmarks.


  • 0

    @StefanPochmann thx~
    btw here is my solution, same idea, more lines...

    def largestDivisibleSubset(self, nums):
            if len(nums)==0:
                return []
            nums.sort()
            d = {i:set([i]) for i in range(len(nums))}
            max_cnt = -1
            max_i = -1
            for i in range(len(nums)):
                max_j = -1
                max_len = -1
                for j in range(i):
                    if nums[i]%nums[j]==0 and len(d[j])>max_len:
                        max_j = j
                        max_len = len(d[j])
                if max_j<>-1:
                    d[i] |= d[max_j]
                if len(d[i])>max_cnt:
                    max_cnt = len(d[i])
                    max_i = i
            #pprint(d)
            return [nums[k] for k in d[max_i]]
    

    excited to use markdown in leetcode!


  • 2

    @MingHan1990 set([i]) is for noobs, try {i} :stuck_out_tongue:


  • 0

    @StefanPochmann thx, always learnt a lot from your code. Actually, i am your fan at leetcode from china and i love python very much, excited to communicate with u~


  • 0
    D

    I'm one of your fans.
    I like your code. Sometimes, your code give me challenge to understand since there are always something I don't understand.

    I like learning from your code.
    I'd like learn the way(EndToEnd) how you approach to problem as well.

    Currenlty, my DP skill is not good.
    I've googled about DP to learn or get some idea, but I don't get it.

    If you can explain how you get a idea for problem, plz share in your post.
    Then, I can follow up.

    Thank you always.


  • 0
    B

    nice code ! thx


  • 0
    W

    is this O(n^3)?


  • 2

    @weiheng4 said in 4 lines in Python:

    is this O(n^3)?

    Yes. But it's also O(n^2).


  • 1

    @tototo said in 4 lines in Python:

    Great solution. About the base case, I think we can simply use 1 instead of -1.

    Yes, you're right, thanks. Not sure I had thought about that. Probably not. I just wanted some "worthless" base case default. But you're right, if 1 isn't among nums then it serves that purpose just as well, and if it is among nums then in the first iteration it'll simply improve that base case (i.e., replace its empty set with {1}). I'll keep it with -1, though, as I find it a little cleaner.


  • 0
    W

    @StefanPochmann what's also n^2 mean?


  • 1

    @weiheng4 said in 4 lines in Python:

    @StefanPochmann what's also n^2 mean?

    @weiheng4 It means exactly that. The solution is both O(n^3) and O(n^2).


  • 1

    @weiheng4 do you know what big-O notation means? I mean, the definition of g(n) = O(f(n)).


  • 0
    W

    @agave
    well, I knowS[d] for d in S if x % d == 0is O(n), max() is O(n), for x in sorted(nums)is O(n), so it's O(n^3). Sorry I don't know why it is also O(n^2)


  • 1

    @weiheng4 Why do you multiply the O(n) for S[d] for d in S if x % d == 0 with the O(n) for max() instead of adding them?


  • 0
    W

    @StefanPochmann
    oh yes, my wrong, sorry. But now, why it is also O(n^3). 😂


  • 1

    @weiheng4 said in 4 lines in Python:

    why it is also O(n^3)

    Trivially so. Every O(n^2) solution is also an O(n^3) solution. Just like everything that doesn't cost more than $2 also doesn't cost more than $3.


Log in to reply
 

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