0435MediumArrayMathDynamic ProgrammingSorting

Rate-Compatible Reel Bundles

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def largest_divisible_subset(samples: list[int]) -> list[int]:

Java

public List<Integer> largestDivisibleSubset(int[] samples)

The intended approach

Time O(n^2): sorting is O(n log n) and each of the n positions scans the positions above it once, with the rebuild bounded by the same scans.Space O(n): the sorted copy, the per-position sizes and the returned listing.

Sort the counts ascending. In that order a bundle is a run in which every count divides the next, so for each position work out the size of the biggest bundle whose smallest member sits there, filling those sizes in from the largest count backwards with one scan of the counts above each position. The biggest of those sizes is the answer's length. Rebuilding the listing then obeys the tie-break directly: start at the earliest position carrying that size, and at every step move to the earliest later count that is a multiple of the current one and carries a size exactly one smaller.

Pythonentry point: largest_divisible_subset

def largest_divisible_subset(samples):
    # Sorted ascending, a bundle is exactly a run of counts in which each one
    # divides the next, because divisibility between the extremes follows from
    # the steps between them. reach[i] holds the size of the biggest bundle whose
    # smallest member sits at position i; filling it from the largest count
    # downwards needs one scan per position. The lexicographic rule then comes
    # from a greedy walk: begin at the earliest position with the top reach, and
    # each step take the earliest larger multiple whose reach is one lower.
    # O(n^2) time, O(n) space.
    order = sorted(samples)
    n = len(order)
    reach = [1] * n
    for i in range(n - 2, -1, -1):
        best = 1
        for j in range(i + 1, n):
            if order[j] % order[i] == 0 and reach[j] + 1 > best:
                best = reach[j] + 1
        reach[i] = best
    target = max(reach)
    cur = 0
    while reach[cur] != target:
        cur += 1
    bundle = [order[cur]]
    need = target - 1
    while need > 0:
        for j in range(cur + 1, n):
            if order[j] % order[cur] == 0 and reach[j] == need:
                cur = j
                bundle.append(order[j])
                need -= 1
                break
    return bundle

The obvious version

Enumerate every subset of the sorted counts, check all pairs inside it for rate compatibility, and keep the best subset seen under the stated rule: more reels wins, and among equals the lexicographically earlier listing wins. Exponential in the number of reels.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_largest_divisible_subset(samples):
    order = sorted(samples)
    n = len(order)
    best = []
    for mask in range(1, 1 << n):
        pick = [order[i] for i in range(n) if (mask >> i) & 1]
        good = True
        for a in range(len(pick)):
            for b in range(a + 1, len(pick)):
                if pick[b] % pick[a] != 0 and pick[a] % pick[b] != 0:
                    good = False
                    break
            if not good:
                break
        if not good:
            continue
        if len(pick) > len(best) or (len(pick) == len(best) and pick < best):
            best = pick
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in