Ctrl K

Отрезать до кратной суммы

Средняя
Дан массив положительных чисел values и число divisor. Из массива можно вырезать один непрерывный отрезок (в том числе пустой), но не весь массив целиком. Найдите длину самого короткого такого отрезка, после удаления которого сумма оставшихся элементов делится на divisor. Если это невозможно, верните -1.
Пример 1
values=[4, 7, 2, 5], divisor=5 → 3

Сумма 18. Ни один элемент и ни одна пара соседей не подходят: после удаления остаются 14, 11, 16, 13, 7, 9, 11. Если вырезать [4, 7, 2], остаётся 5 — ответ 3.

Пример 2
values=[6, 1, 8], divisor=7 → 1

Сумма 15, убираем 1 — остаётся 14.

Пример 3
values=[3, 3], divisor=4 → -1

Убрать одну тройку — остаётся 3, убрать обе нельзя. Ответ −1.

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

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