Finding maximum number of congruent numbers
- by Stefan Czarnecki
Let's say we have a multiset (set with possible duplicates) of integers. We would like to find the size of the largest subset of the multiset such that all numbers in the subset are congruent to each other modulo some m 1.
For example:
1 4 7 7 8 10
for m = 2 the subsets are: (1, 7, 7) and (4, 8, 10), both having size 3.
for m = 3 the subsets are: (1, 4, 7, 7, 10) and (8), the larger set of size 5.
for m = 4 the subsets are: (1), (4, 8), (7, 7), (10), the largest set of size 2.
At this moment it is evident that the best answer is 5 for m = 3.
Given m we can find the size of the largest subset in linear time.
Because the answer is always equal or larger than half of the size of the set, it is enough to check for values of m upto median of the set.
Also I noticed it is necessary to check for only prime values of m.
However if values in the set are large the algorithm is still rather slow.
Does anyone have any ideas how to improve it?
