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
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.
1 >>> a = [1, 2, 3] 2 >>> a[-1] 3 3
Get premium for instant access to all content and solutions