Find subset of points whose distance among each other is a multiple of a number

Question

The problem: given an array A which represents points on a line, e.g. [5,-4,1,3,6], and a number M=3, find the maximal subset of points within A whose distance among each other is a multiple of M.

In the example, the two possible subsets would be [-4,5] (distance 9) and [3,6] (distance 3).

The obvious brute force solution would be to compute the distance between each pair of points in O(N^2) time, then build a set of candidates by incrementally building up the subsets.

Is there a more efficient solution?

Answer 1

Iterate over the numbers in the array and compute the modulus M of each, and group by the result. The largest group is the maximal subset.

e.g. [5,-4,1,3,6] would give [2,2,1,0,0]

You'd have to take care how you handle negative numbers, the modulus operation for negatives is defined differently in some languages (e.g. PHP) to others, but you would want mod(-4, 3) to evaluate to 2, not -1. For negatives you could compute it as (M - (-x mod M)) mod M

You could efficiently group the numbers by storing a hash map of lists containing the numbers, keyed on the modulus.