25 подписчиков
Решал задачи на алгоритмы.
Задача:
Дано массив из n натуральных чисел.
Дано натуральное число k.
Найти – количество неупорядоченных пар элементов, где разность элементов пары делится на k.
Разумеется, с ходу находится решение в виде брутфорса, временная сложность O(n²), пространственная сложность O(1).
Неинтересно – декларируется, что есть решение с меньшей временной сложностью.
Думая совсем о другой задаче (точнее, о том, почему предлагаемое к ней решение даёт верный результат, что для меня было совсем не очевидно), ВНЕЗАПНО™ догадался, как решать эту.
А вы подумайте.
Очень жирная подсказка: найденное решение даёт временную сложность O(n) и пространственную сложность O(k).
Около минуты
28 августа 2023