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:
1nums = [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:
1nums = [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) <= 10001 <= nums[i] <= 10^9- Each number in
numsis unique