Ctrl K

Лучшая стартовая метка

Средняя
На прямой стоят метки, их координаты — массив положительных чисел marks (значения могут повторяться). Кузнечик начинает на одной из меток и дальше прыгает только вперёд, каждый раз ровно на stride. Он побывает в точках v, v + stride, v + 2·stride, … и накроет все метки с такими координатами. Стартовой точкой может быть только значение из marks. Выберите старт, при котором накрыто как можно больше меток (каждый элемент массива считается отдельно). Если таких стартов несколько, верните наименьший.
Пример 1
marks=[4, 10, 7, 1, 13, 2], stride=3 → 1

Старт с 1 даёт прыжки 1, 4, 7, 10, 13, … — накрыты пять меток из шести, все кроме 2.

Пример 2
marks=[9, 5, 14, 6], stride=4 → 5

Старт с 5 накрывает 5 и 9, старт с 6 — 6 и 14. По две метки в обоих случаях, выбираем меньшее число — 5.

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

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