Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
I think (2, 8, 10) should be (4, 8, 10) for m = 2. –  Mathew Foscarini May 27 '13 at 15:58
    
Of course, edited. –  Stefan Czarnecki May 27 '13 at 16:37
    
I don't see how your example shows congruent numbers. 1, 4, 8, 10 are not congruent. right? –  Mathew Foscarini May 27 '13 at 16:41
    
They are not. (4, 8, 10) are congruent for m=2 though and so are (1, 7, 7). –  Stefan Czarnecki May 27 '13 at 16:45

1 Answer 1

There may be a way to evaluate the results for several m values with one pass through the multiset - possibly even all of them - though it means deriving another (hopefully smaller) collection of partitions to loop through.

Take the first three m values - as you only need to consider primes, that's 2, 3 and 5. The product of those is 30. So partition the multiset into equivalence classes modulo 30.

Now you can determine the sizes/subsets for m=2, m=3 and m=5 relatively easily. Each m=2 subset consists of every other partition from those 30, each m=3 subset consists of every third partition, and each m=5 subset consists of every fifth partition. With an array of 30 partitions (e.g. linked list heads) to consider, that's much less work than partitioning the whole initial multiset three times. Instead of doing pn classifications, you do n+pq where p is the number of primes for the pass (3 here) and q is the product of those primes (30 for 2, 3 and 5). If n is large enough and q is small enough, this should be a net gain, but q grows rapidly as the number/size of the primes grows.

As q gets larger, it may be possible to reduce the +pq part by tracking which of the modulo values actually occurred in the initial loop - e.g. building a linked list. To be honest, though, I suspect the added complexity would outweigh any gains.

I'm not sure if there's a workable idea in this or not - even if you can build something that works, it's likely that a more complex algorithm will be slower. But maybe there's the core of an idea here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.