repeating elements in an array
in [General Programming]
|
From: mohangupta13 on 16 Apr 2010 06:30 On Apr 6, 5:47 pm, mohangupta13 <mohangupt...(a)gmail.com> wrote: > first of all. thanks a lot for your answers ... > > On Apr 6, 1:57 am, Richard Heathfield <r...(a)see.sig.invalid> wrote: > > > > > mohangupta13 wrote: > > > hello all, > > > Hope everyone is in the pink of perfection ! ...i was out for a long > > > time i think .. > > > > anyway i had two problems to discuss ... > > > > 1. Given an array in which only one pair of number ( say integers ) is > > > repeating ,all other numbers are distinct ..what is the best possible > > > algo to find such number ..?? ( say for both cases when we dont have > > > any constraint on the numbers and when we do define some constrain say > > > the range of possible numbers in the array)... > > > Lacking a definition of "best", the simplest way is to sort the array, > > and then iterate through it looking for adjacent elements with the same > > value. > > for the first problem what if we have a constraint that the range of > numbers is between [0----kn] for some constant k...now what is the > best possible way to do this ?? > ( and is it possible in O(n) time with using a constant storage ..and > if not how can we prove that fact ???) > > > > > > 2. (this may not be suited here but still ) What is the probability > > > that out of 5 persons, no two person have birthday on the same day of > > > a week (..i.e all 5 have birthdays on different days of a week)..??? > > > 7! / (7-5)! > > ----------- > > 5 > > 7 > > > = 7 * 6 * 5 * 4 * 3 > > ----------------- > > 7 * 7 * 7 * 7 * 7 > > > = 360/2401, or slightly over 0.14993752603. > > > -- > > Richard Heathfield <http://www.cpax.org.uk> > > Email: -http://www. +rjh@ > > "Usenet is a strange place" - dmr 29 July 1999 > > Sig line vacant - apply within > > regards, > Mohan one technique that i came across if we have a constraint on the range of numbers (say 0-k) is we can have a bit vector of length lg(k) and set its i'th bit each time we encounter a number with value i. so now if we get a number say x twice , the second occurence of x will find bit at location x to be set indicating that we have already seen x. hence the space required is O(lg k). Now what doubts me still is ...had we had many pairs of repeated numbers ( event without any range constraint) we could have sorted them and found out who all are repeating in o(nlg n) time ....but now we are explicitly given that we just have a single pair that is repeating , so can't we do better ....???? and can we prove it deterministically that any further improvement is impossible or is there a way to guess that intuitively for this particular problem and such problems is general ??? thanks a lot Mohan
From: mohangupta13 on 16 Apr 2010 06:31 On Apr 6, 12:57 am, Kai-Uwe Bux <jkherci...(a)gmx.net> wrote: > mohangupta13 wrote: > > hello all, > > Hope everyone is in the pink of perfection ! ...i was out for a long > > time i think .. > > > anyway i had two problems to discuss ... > > > 1. Given an array in which only one pair of number ( say integers ) is > > repeating ,all other numbers are distinct ..what is the best possible > > algo to find such number ..?? ( say for both cases when we dont have > > any constraint on the numbers and when we do define some constrain say > > the range of possible numbers in the array)... > > I would start with: > > a) sort the array > b) find the two equal (and now adjacent!) slots > > Now, if there is some constraint, it would be cool to know the constraint.. > E.g., if the array has length n and the integers are from [0,n), then one is > repeating and one is missing, and you can find out which by adding all > numbers in the array (mod n). > > > 2. (this may not be suited here but still ) What is the probability > > that out of 5 persons, no two person have birthday on the same day of > > a week (..i.e all 5 have birthdays on different days of a week)..??? > > 7/7 * 6/7 * 5/7 * 4/7 *3/7 \approx 0.15 > > (the first is free, the second has to avoid one day of the week, two days > are blocked for the 3rd, ...) > > Also: google "birthday paradox". > > Best > > Kai-Uwe Bux one technique that i came across if we have a constraint on the range of numbers (say 0-k) is we can have a bit vector of length lg(k) and set its i'th bit each time we encounter a number with value i. so now if we get a number say x twice , the second occurence of x will find bit at location x to be set indicating that we have already seen x. hence the space required is O(lg k). Now what doubts me still is ...had we had many pairs of repeated numbers ( event without any range constraint) we could have sorted them and found out who all are repeating in o(nlg n) time ....but now we are explicitly given that we just have a single pair that is repeating , so can't we do better ....???? and can we prove it deterministically that any further improvement is impossible or is there a way to guess that intuitively for this particular problem and such problems is general ??? thanks a lot Mohan
From: Patricia Shanahan on 16 Apr 2010 08:32 mohangupta13 wrote: .... > one technique that i came across if we have a constraint on the range > of numbers (say 0-k) is we can have a bit vector of length lg(k) > and set its i'th bit each time we encounter a number with value i. so > now if we get a number say x twice , the second occurence of x will > find bit at location x to be set indicating that we have already seen > x. hence the space required is O(lg k). .... Are the bounds inclusive or exclusive? Assuming 0 through k, you need a k+1 bit vector, and O(k) space. Think about the "i'th bit" for inputs 0 and k. Patricia
From: Richard Harter on 16 Apr 2010 11:15 On Mon, 5 Apr 2010 12:14:29 -0700 (PDT), mohangupta13 <mohangupta13(a)gmail.com> wrote: >hello all, >Hope everyone is in the pink of perfection ! ...i was out for a long >time i think .. > >anyway i had two problems to discuss ... > >1. Given an array in which only one pair of number ( say integers ) is >repeating ,all other numbers are distinct ..what is the best possible >algo to find such number ..?? ( say for both cases when we dont have >any constraint on the numbers and when we do define some constrain say >the range of possible numbers in the array)... Several people have suggested sorting the array. However the problem doesn't say anything about limitations on space, so why not put the numbers into a hash table and stop when you hit a duplicate. on average the performance is O(n). Granted that the worst case is O(n^2) but one can always use a sort as a backup. Alternatively, a bloom filter would be fun. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com It's not much to ask of the universe that it be fair; it's not much to ask but it just doesn't happen.
From: mohangupta13 on 19 Apr 2010 01:37 On Apr 16, 8:15 pm, c...(a)tiac.net (Richard Harter) wrote: > On Mon, 5 Apr 2010 12:14:29 -0700 (PDT), mohangupta13 > > <mohangupt...(a)gmail.com> wrote: > >hello all, > >Hope everyone is in the pink of perfection ! ...i was out for a long > >time i think .. > > >anyway i had two problems to discuss ... > > >1. Given an array in which only one pair of number ( say integers ) is > >repeating ,all other numbers are distinct ..what is the best possible > >algo to find such number ..?? ( say for both cases when we dont have > >any constraint on the numbers and when we do define some constrain say > >the range of possible numbers in the array)... > > Several people have suggested sorting the array. However the > problem doesn't say anything about limitations on space, so why > not put the numbers into a hash table and stop when you hit a > duplicate. on average the performance is O(n). Granted that the > worst case is O(n^2) but one can always use a sort as a backup. > Alternatively, a bloom filter would be fun. I am afraid if i didn't mention that in my first post ...but the whole point what i was trying to make is to get a fastest solution with a minimum amount of space ... say if the numbers are from [0,k) ( an half open interval) in an array of size n ....and we want an algo possible O(n) time with minimum space . thanks > > Richard Harter, c...(a)tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com > It's not much to ask of the universe that it be fair; > it's not much to ask but it just doesn't happen.
First
|
Prev
|
Pages: 1 2 Prev: The RUN CHASE: A Challenge for the Programmer in U... Next: "Variable Depth" Problem |