Show problems as
Classic problem #2344HardArrayMathSortingHeap (Priority Queue)Number TheoryEuclidean AlgorithmGreatest Common Divisor

Minimum Deletions to Make Array Divisible

Real-world version: Discarding Tiles Until the Walls Fit
Tracked in this browser only
Read Minimum Deletions to Make Array Divisible on LeetCode(opens in a new tab)

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

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

Python
def fewest_discards(tiles: list[int], walls: list[int]) -> int:
Java
public int fewestDiscards(int[] tiles, int[] walls)

More on the same topics