0821HardArrayMathSortingHeap (Priority Queue)Number TheoryEuclidean AlgorithmGreatest Common Divisor

Discarding Tiles Until the Walls Fit

Tracked in this browser only

Trains the technique from

LeetCode 2344Minimum Deletions to Make Array Divisible

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.

A tiling crew keeps a bag of square tiles, where tile i has side length tiles[i]. It also holds a job sheet of wall widths, given as walls.

The crew always lays whichever side length is smallest in the bag, and a wall can be tiled only when that side length divides the wall's width exactly. So the bag is ready for the job sheet when the smallest side length in it divides every width in walls.

One discard removes exactly one tile whose side length is the smallest currently in the bag. When several tiles share that smallest side length, one discard takes only one of them, so the smallest side length does not change until every copy of it is gone.

Return the fewest discards that leave the bag ready for the job sheet. An empty bag has no smallest side length and so is never ready. If no number of discards leaves the bag ready, return -1.

Examples

Example 1

Input: tiles = [5, 4, 4, 7, 10], walls = [20, 50]
Output: 2

After two discards, both of them tiles of side 4, the bag holds sides 5, 7 and 10. The smallest of those is 5, and 5 divides 20 as well as 50, so the bag is ready.

Example 2

Input: tiles = [6, 4, 10, 4], walls = [20, 40, 60]
Output: 0

The bag already holds 4 as its smallest side, and 4 divides 20, 40 and 60, so no discard is needed.

Example 3

Input: tiles = [4, 6], walls = [9, 15]
Output: -1

With both tiles in the bag the smallest side is 4, which does not divide 9. Discarding the tile of side 4 leaves 6 as the smallest, and 6 does not divide 9 either, while a further discard empties the bag.

Constraints

1 <= tiles.length <= 10^5
1 <= walls.length <= 10^5
1 <= tiles[i] <= 10^9
1 <= walls[i] <= 10^9

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 fewest_discards(tiles: list[int], walls: list[int]) -> int:

Java

public int fewestDiscards(int[] tiles, int[] walls)

The intended approach

Time O(n log n + m log W) for n tiles, m walls and widths up to W.Space O(n) for the sorted copy of the side lengths.

A side length divides every width exactly when it divides the greatest common divisor of the widths, so fold the job sheet into that single number first. Then sort the side lengths and take the first one that divides it: everything ahead of that position has to be discarded and everything from it onwards stays, so the position itself is the answer. Running off the end of the sorted sides means no side length ever fits.

Pythonentry point: fewest_discards

def fewest_discards(tiles, walls):
    # A side divides every width exactly when it divides their greatest common
    # divisor, so the whole wall list collapses to one number. Sorting the sides
    # then makes the first side that divides it the one that survives, and its
    # position is how many sides had to go.
    # Time: O(n log n + m log W) for n tiles, m walls and widths up to W.
    # Space: O(n) for the sorted copy of the sides.
    shared = 0
    for width in walls:
        a, b = shared, width
        while b:
            a, b = b, a % b
        shared = a
    for pos, side in enumerate(sorted(tiles)):
        if shared % side == 0:
            return pos
    return -1

The obvious version

Carry the discards out literally. Find the smallest side length in the bag, test it against each width one at a time, and if any width refuses it, remove a single copy of that side length and start over. Reaching an empty bag means the job sheet can never be met.

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_fewest_discards(tiles, walls):
    """Play the discards out one at a time: look at the smallest side in the bag,
    test it against every width on its own, and if it fails throw one copy of it
    away and look again."""
    bag = list(tiles)
    thrown = 0
    while bag:
        smallest = min(bag)
        fits = True
        for width in walls:
            if width % smallest != 0:
                fits = False
                break
        if fits:
            return thrown
        bag.remove(smallest)
        thrown += 1
    return -1

How this problem was checked

Reference solution executed against 21 test cases — 21 passed
3 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