Тяжело · 5 очковЕГЭ задание 27Остатки по модулюЭффективный алгоритм2 решили

ЕГЭ №27: число пар с суммой, кратной K, за O(n)

Дан список целых чисел nums и число k. Нужно посчитать количество пар индексов i < j, для которых сумма nums[i] + nums[j] кратна k.

Наивное решение перебирает все пары за O(n^2). Требуется эффективное решение за O(n + k): подсчитать, сколько чисел даёт каждый остаток по модулю k, а затем скомбинировать остатки r и k - r (отдельно обработав остаток 0 и, при чётном k, остаток k/2).

Функция count_pairs_div(nums, k) возвращает целое число — количество подходящих пар.

Вход: nums — список целых чисел (может быть пустым); k >= 1. Выход: целое неотрицательное число.

Примеры:

count_pairs_div([1, 2, 3, 4, 5], 3) -> 4
count_pairs_div([3, 6, 9], 3)       -> 3
count_pairs_div([1, 1, 1, 1], 2)    -> 6

Теория: Задание 27: эффективный алгоритм анализа последовательности

Курс по теме: Python с нуля — 8 уроков, по шагам и с проверкой

Python
def count_pairs_div(nums, k):
    # ваш код
    pass

Нажми «Проверить код» — прогоним тесты и покажем, что не так, если не пройдут.

Ctrl↵ проверить

Проверять можно без входа. , чтобы решение и очки сохранились.