Show problems as
Classic problem #368MediumArrayMathDynamic ProgrammingSorting

Largest Divisible Subset

Real-world version: Rate-Compatible Reel Bundles
Tracked in this browser only
Read Largest Divisible Subset on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

An audio restoration lab logs the length of every reel it holds as a whole number of samples. The log, samples, holds one count per reel and no two counts are equal.

Two reels are rate-compatible when one reel's count is a whole multiple of the other's, in whichever direction that happens to hold.

A bundle is a set of reels in which every pair of reels is rate-compatible. A bundle holding a single reel therefore always qualifies.

Return the counts of a bundle holding as many reels as possible, listed in increasing order. Where several bundles are equally large, return the one whose increasing listing comes first lexicographically: read the two listings position by position and prefer the listing with the smaller count at the first position where they differ.

Examples

Example 1

Input
samples = [8, 2, 4, 3]
Output
[2, 4, 8]

Two divides four, two divides eight and four divides eight, so those three reels are pairwise rate-compatible and the listing is in increasing order.

Example 2

Input
samples = [3, 4, 8, 16]
Output
[4, 8, 16]

Within four, eight and sixteen every pair has one count as a whole multiple of the other.

Example 3

Input
samples = [1, 2, 4, 6]
Output
[1, 2, 4]

Both [1, 2, 4] and [1, 2, 6] hold three pairwise compatible reels, and the tie-break prefers the first, since four is below six at the earliest position where the two listings differ.

Example 4

Input
samples = [2, 3]
Output
[2]

Neither count is a whole multiple of the other, so these two reels are not rate-compatible and each stands alone as a bundle; the tie-break prefers the listing with the smaller count.

Constraints

  • 1 <= samples.length <= 1000
  • 1 <= samples[i] <= 2 * 10^9
  • All the counts in samples are distinct.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def largest_divisible_subset(samples: list[int]) -> list[int]:
Java
public List<Integer> largestDivisibleSubset(int[] samples)

More on the same topics