wu :: forums - Print Page


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

        riddles >> cs >> find the common element
        
(Message started by: RamRaul on Feb 2^nd, 2010, 4:23am)

Title: find the common element
Post by RamRaul on Feb 2^nd, 2010, 4:23am

You have 3 arrays containing 200 integers each. Given that there is one and only one common element in these 3 arrays. Find the common element.

any suggestions how to proceed ???

Title: Re: find the common element
Post by towr on Feb 2^nd, 2010, 4:29am

You could sort the arrays, then do a traversal where you increment the index into an array if its corresponding value is smaller than the value at the indices of the other two array.

Title: Re: find the common element
Post by Grimbal on Feb 2^nd, 2010, 5:47am

... smaller than one of the values at the indices of the other two array.

Title: Re: find the common element
Post by towr on Feb 2^nd, 2010, 5:59am

Hmm, yeah, that's better. Otherwise you can get stuck when the two lowest ones are equal.
I was thinking of just always incrementing the least value, but then I should have phrased it differently.

Title: Re: find the common element
Post by RamRaul on Feb 3^rd, 2010, 4:24am

@towr:thank u..thats workin

what i was thinking was to hash two of the arrays and run lookups from the third, which takes O(n) steps and O(n log n) bits of space.
bt i dont think that dere's improvement in complexity than the method u explained!!!!!!!

Title: Re: find the common element
Post by towr on Feb 3^rd, 2010, 4:38am

If the arrays were very large (much, much larger than 200 integers), than using hashing would probably be more time efficient. Just as long as the hashing/lookup takes less than O(log(n)) time per item.

Title: Re: find the common element
Post by bmudiam on Feb 8^th, 2010, 7:21pm

If the elements are all prime numbers, then you can actually multiply the elements in first array, then second array and then third array and see if there is any common factor of a *b and b *c.

Can we make this solution work for non-prime number s too?

Title: Re: find the common element
Post by Obob on Feb 8^th, 2010, 8:18pm

If the integers are all positive, say the integers in the first array are a_i, then you can take the product of the numbers p(a_i), where p(a) is the a-th prime number. Then take the GCD of the three numbers obtained in this way to get a prime, and figure out which prime it is to get the answer. You can easily adapt this to all integers. This is clearly a bad way to do it though, and you'll have overflow errors very quickly.