ЕГЭ №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 уроков, по шагам и с проверкой
def count_pairs_div(nums, k):
# ваш код
pass
Нажми «Проверить код» — прогоним тесты и покажем, что не так, если не пройдут.
Проверять можно без входа. , чтобы решение и очки сохранились.