Ctrl K

Меньше видов после удаления

Средняя
В коробке лежат детали, items[i] — вид i-й детали. Нужно выбросить ровно removals деталей так, чтобы в коробке осталось как можно меньше разных видов. Верните это наименьшее число видов.
Пример 1
items=[7, 7, 2, 9, 9, 9], removals=2 → 2

Выбрасываем обе семёрки — остаются виды 2 и 9. Убрать за два удаления два вида нельзя: самый редкий (2) стоит одно удаление, следующий (7) — ещё два.

Пример 2
items=[4, 1, 4, 3], removals=4 → 0

Убираем всё, видов не остаётся.

Пример 3
items=[5, 6, 5], removals=0 → 2
Ограничения
  • 1 ≤ len(items) ≤ 10⁵
  • 1 ≤ items[i] ≤ 10⁹
  • 0 ≤ removals ≤ len(items)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЗадания с перерывом на остывание СредняяМетки вразнобой СредняяВыбор с лимитом по тегам СредняяПалиндромы из общих букв СредняяБольше трети голосов Средняя
загружаем Python…
Вход
items=[7, 7, 2, 9, 9, 9], removals=2
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 72 теста на сервере, включая скрытые.