Author |
Topic: find the common element (Read 718 times) |
|
RamRaul
Newbie
 
Gender: 
Posts: 5
|
 |
find the common element
« on: Feb 2nd, 2010, 4:23am » |
 Quote  Modify
|
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 
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the common element
« Reply #1 on: Feb 2nd, 2010, 4:29am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: find the common element
« Reply #2 on: Feb 2nd, 2010, 5:47am » |
Quote Modify
|
... smaller than one of the values at the indices of the other two array.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the common element
« Reply #3 on: Feb 2nd, 2010, 5:59am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 2nd, 2010, 6:01am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
RamRaul
Newbie
Gender:
Posts: 5
|
|
Re: find the common element
« Reply #4 on: Feb 3rd, 2010, 4:24am » |
Quote Modify
|
@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!!!!!!!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the common element
« Reply #5 on: Feb 3rd, 2010, 4:38am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: find the common element
« Reply #6 on: Feb 8th, 2010, 7:21pm » |
Quote Modify
|
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?
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: find the common element
« Reply #7 on: Feb 8th, 2010, 8:18pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print