Finding maximum number of congruent numbers

Posted by Stefan Czarnecki on Programmers See other posts from Programmers or by Stefan Czarnecki
Published on 2013-05-27T14:02:29Z Indexed on 2013/06/26 22:29 UTC
Read the original article Hit count: 223

Filed under:
|

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?

© Programmers or respective owner

Related posts about algorithms

Related posts about math