Найти подмножество точек, расстояние между которыми кратно числу

Question

Проблема: задан массив A, который представляет точки на линии, например. [5,-4,1,3,6] и номер M=3, найдите максимальное подмножество точек в пределах A, расстояние между которыми несколько кратно M.

В этом примере двумя возможными подмножествами будут [-4,5] (расстояние 9) и [3,6] (расстояние 3).

Очевидным решением для перебора является вычисление расстояния между каждой парой точек в O(N^2) времени, а затем построение набора кандидатов путем постепенного наращивания подмножеств.

Есть ли более эффективное решение?

Answer 1

Итерируйте по номерам в массиве и вычислите модуль M каждого из них и сгруппируйте по результату. Наибольшая группа - максимальное подмножество.

например. [5,-4,1,3,6] даст [2,2,1,0,0]

Вы должны были бы заботиться, как вы справиться с отрицательными числами, то операция модуля для негативов определяются differently in some languages (например, PHP) для других, но вы хотели бы мод (-4, 3) оценить, 2, а не -1. Для негативов вы можете вычислить его как (M - (-x mod M)) mod M

Вы можете эффективно группировать числа, сохраняя хэш-карту списков, содержащих числа, заданные по модулю.