Largest Divisible Subset
Given a set of distinct positive integers, find the size of the largest subset in which every pair of numbers satisfies the divisibility condition: for any two members, one divides the other.
Input & Output
Input
nums — a list of distinct positive integers representing the set
Output
the size of the largest subset in which one number of every pair divides the other
Example
Input
nums = [1, 2, 3]
Output
2
Explanation
Either [1, 2] or [1, 3] satisfies the condition, because both 2 and 3 are divisible by 1. Adding the third number breaks it, since 3 % 2 != 0 and 2 % 3 != 0, so the largest subset has size 2.
Example
Input
nums = [1, 2, 4, 8]
Output
4
Explanation
The whole set qualifies, since 8 % 4 == 0, 8 % 2 == 0, 8 % 1 == 0, 4 % 2 == 0, 4 % 1 == 0, and 2 % 1 == 0.
Example
Input
nums = [8, 9, 4, 2, 12, 1, 3]
Output
4
Explanation
{1, 2, 4, 8} works, and so does {1, 2, 4, 12}. Adding 3 to either breaks the condition because 3 neither divides 4 nor is divisible by it, so no subset of size 5 exists.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 10^9- All integers in
numsare distinct