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.

Input

  • nums: a list integers representing the set.

Output

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

Examples

Example 1:

Input:

nums = [1, 2, 3]

Output: 2

Explanation:

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:

Input:

nums = [1, 2, 4, 8]

Output: 4

Explanation:

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.

Constraints

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

Try it yourself

Solution

Title

Script

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.

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

Get premium for instant access to all content and solutions

Upgrade