Largest Divisible Subset

You are given a set of numbers nums consisting of distinct numbers. Find the size of the largest subset that satisfies the following condition: for each two number pairings in the set, one number is divisible by the other.


  • nums: a list integers representing the set.


An integer representing the size of the largest subset that satisfy the condition.


Example 1:


1nums = [1, 2, 3]

Output: 2


Either [1, 2] or [1, 3] satisfy the condition, because both 2 and 3 are both divisible by 1. Either way, the largest set has a size of 2.

Example 2:


1nums = [1, 2, 4, 8]

Output: 4


In this set, for each pair of numbers, at least one is divisible by the other because they are all powers of 2. As such, the max subset has a size of 4, the size of the original set.


  • 1 <= len(nums) <= 1000
  • 1 <= nums[i] <= 10^9
  • Each number in nums is unique

Try it yourself




Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions