Войти Регистрация
Алгоритмы

133. Отрезки операций с круглой суммой

Средняя

В выписке Альфа‑Банка операции по карте идут подряд: amounts[i] в рублях, покупки положительные, возвраты отрицательные.

Посчитайте, сколько непустых отрезков подряд идущих операций дают в сумме число, кратное k. Ноль тоже кратен k.

В работе: Акция «каждые 500 ₽ покупок — балл»: аналитики ищут, как часто серии операций дают ровно целое число баллов.

Пример 1

Ввод
amounts = [300, 200, -100, 600, 500]
k = 500
Вывод
6

Шесть отрезков, среди них [300, 200], [−100, 600], [500] и вся выписка (1500 ₽).

Пример 2

Ввод
amounts = [7]
k = 5
Вывод
0

7 не делится на 5.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • −10⁶ ≤ amounts[i] ≤ 10⁶
  • 1 ≤ k ≤ 10⁴
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def divisible_runs(amounts, k):
Префиксные суммыХеш-таблицаОстаткицельO(n)

Источник: наша задача на данных Альфа-Банка. Условие пересказано своими словами.