O(n * sqrt(n)) Solution in Python beats 99%


  • 0
    G

    An observation here: given a sorted set S = {x_1, x_2, ..., x_k}, we have x_i | x_j for any 1 <= i < j <= k.

    Thus, the basic idea is: given an element $x$, instead of enumerating the "previous" element in the subset, we enumerate the divisors of $x$. Say the list of divisors of $x$ is given by $d_1, d_2, ..., d_l$, we have the following recursion:
    dp[x] = max(dp[d_i] + 1), 1 <= i <= l

    A naive approach for obtaining the divisors of an positve integer $n$ is, simply enumerate all the integers in the range of [1, \sqrt(n)]. This already gives us an $O(n * \sqrt(n))$ solution. Of course there are better algorithms for doing this, but this one is good enough for this problem.

    My (ugly) code:

    from collections import defaultdict
    
    class Solution(object):
        def getDivisors(self, n):
            k = 1
            divs = []
            while k * k <= n:
                if n % k == 0:
                    divs.append(k)
                    if k * k != n and k != 1:
                        divs.append(n / k)
                k += 1
            return divs
        
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if len(nums) == 0:
                return []
            dp = defaultdict(int)
            nums = sorted(nums)
            ans, ans_num = 0, 0
            prev = {num: num for num in nums}
            
            for num in nums:
                divs = self.getDivisors(num)
                for d in divs:
                    if dp[d] + 1 > dp[num]:
                        dp[num] = dp[d] + 1
                        if dp[d] >= 1:
                            prev[num] = d
                        if dp[num] > ans:
                            ans, ans_num = dp[num], num
            max_subset = [ans_num]
            while prev[max_subset[-1]] != max_subset[-1]:
                max_subset.append(prev[max_subset[-1]])
            return max_subset
    

  • 0
    Q

    Supposed that the max value in input array nums is x, the time complexity of your post shall be O(nsqrt(x)), not O(nsqrt(n)). I do not know python so I cannot determine the space complexity. But i think in java, if follow your idea, the space complexity is O(x) which is the largest value in input array nums


  • 0
    G

    @QunWu Yes you are right.


Log in to reply
 

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