Show problems as
Classic problem #1838MediumArrayBinary SearchGreedySliding WindowSortingPrefix Sum

Frequency of the Most Frequent Element

Real-world version: Plates at One Thickness
Tracked in this browser only
Read Frequency of the Most Frequent Element on LeetCode(opens in a new tab)

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

A plating shop builds press plates up to size with a spray gun. plates gives the current thickness of each plate in microns, in no particular order, and coating is how many microns of spray are left in the tank altogether.

One micron of spray raises one plate by one micron and draws one micron from the tank. You may spray any plate as often as you like, in any order, but spray can never be stripped back off, so no plate ever gets thinner. You are not obliged to empty the tank.

The press only accepts a batch of plates that all measure exactly the same. Return the largest number of plates that can be brought to one common thickness.

Examples

Example 1

Input
plates = [9, 4, 8, 8, 6], coating = 4
Output
3

Spray 2 microns onto the plate at 6 to bring it to 8. Together with the two plates already at 8 that makes three plates measuring 8, with 2 microns still in the tank.

Example 2

Input
plates = [2, 4], coating = 2
Output
2

Both microns go on the plate at 2, lifting it to 4 so that both plates measure 4.

Example 3

Input
plates = [7, 7, 7, 7], coating = 1
Output
4

All four plates already measure 7, so the batch is complete without spraying anything.

Example 4

Input
plates = [1, 2, 3, 4, 100], coating = 2
Output
2

Spraying 2 microns onto the plate at 2 takes it to 4, which matches the plate already at 4, giving two plates at the same measure.

Constraints

  • 1 <= plates.length <= 10^5
  • 1 <= plates[i] <= 10^5
  • 1 <= coating <= 10^5

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 max_matched_plates(plates: list[int], coating: int) -> int:
Java
public int maxMatchedPlates(int[] plates, int coating)

More on the same topics