diff options
Diffstat (limited to 'largest_divisible_subset.py')
-rw-r--r-- | largest_divisible_subset.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/largest_divisible_subset.py b/largest_divisible_subset.py new file mode 100644 index 0000000..842b78a --- /dev/null +++ b/largest_divisible_subset.py @@ -0,0 +1,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])) |