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

• 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


• 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

• @QunWu Yes you are right.

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