aboutsummaryrefslogtreecommitdiff
path: root/largest_divisible_subset.py
blob: 842b78a38fbe4e78304fb85ca0d6eef0659a7383 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 368. Largest Divisible Subset

"""
given a set of distinct positive integers 'nums', return the largest subset
'answer' such that every pair '(ans[i], ans[j])' of elements in this subset
satifies 'ans[i] % ans[j] == 0' or 'ans[j] % ans[i] == 0'. if there are
multiple solutions, return any of them.
"""


class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) == 0:
            return []
        nums.sort()
        ans = [[i] for i in nums]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0 and len(ans[i]) < len(ans[j]) + 1:
                    ans[i] = ans[j] + [nums[i]]
        return max(ans, key=len)


if __name__ == "__main__":
    obj = Solution()
    print(obj.largestDivisibleSubset([1, 2, 3]))
    print(obj.largestDivisibleSubset([1, 2, 4, 8]))