Ctrl K

Наименьший делит всех

Сложная
Даны два массива положительных целых чисел: values и targets. Из values можно удалить сколько угодно элементов. Нужно добиться, чтобы наименьший из оставшихся в values элементов делил нацело каждое число из targets. Хотя бы один элемент в values должен остаться. Верните минимальное число удалений или -1, если этого добиться нельзя.
Пример 1
values=[8, 6, 4, 12, 6], targets=[18, 30, 12] → 1

Наименьшее 4 не делит 18 и 30. Убираем 4 — наименьшим станет 6, и оно делит 18, 30 и 12. Удалили один элемент.

Пример 2
values=[5, 10], targets=[7, 14] → -1

Ни 5, ни 10 не делят 7, так что ничего не выйдет.

Пример 3
values=[3, 1, 3], targets=[100] → 0
Ограничения
  • 1 ≤ len(values), len(targets) ≤ 10⁵
  • 1 ≤ values[i], targets[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСортировка обменами по общему делителю СложнаяБлижайшие к базе точки СредняяЦена тает с каждой продажей СредняяОдни призы, разные вкусы СредняяТри самых тяжёлых ромба Средняя
загружаем Python…
Вход
values=[8, 6, 4, 12, 6], targets=[18, 30, 12]
Ожидается
1

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