wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find i such that S and (S+i) is maximal
        
(Message started by: cuckoo on Oct 21^st, 2007, 8:12pm)

Title: Find i such that S and (S+i) is maximal
Post by cuckoo on Oct 21^st, 2007, 8:12pm

S is a set of integers. S+i={ x+i | x \in S}. Find an integer such that [ S AND (S+i) ] has maximual number of elements. AND represent set intersection.

Can this problem be solved in less than O(n^2) time? (n=|S|)

Title: Re: Find i such that S and (S+i) is maximal
Post by towr on Oct 22^nd, 2007, 2:25am

You want the maximal intersection? Why not pick i=0?

If you want an i>0, I think you can still do better than O(n²). Maybe use string matching techniques, or something like a convolution (using FFT-like techniques).