Dave tu mahan hai . . . . ---------- Forwarded message ---------- From: "Dipankar Patro" <dip10c...@gmail.com> Date: 14 Aug 2011 23:27 Subject: Re: [algogeeks] Re: array question To: <algogeeks@googlegroups.com>
@Dave nice algo. Really like it. So the whole complexity depends on the sorting. On 14 August 2011 22:58, Dave <dave_and_da...@juno.com> wrote: > @Dipankar: If extra space is not allowed, I think the optimal solution > is to sort the two arrays, which takes O(max(m log m, n log n)). Then > the common element can be found in O(m + n) by a simple search that > starts at i = j = 0 and increments the index of the lesser of a[i] and > b[j]. Overall complexity is O(max(m log m, n log n)). > > Dave > > On Aug 14, 8:24 am, Dipankar Patro <dip10c...@gmail.com> wrote: > > @ Sagar: > > What if extra space in not allowed? > > I think then we have to use the binary search method... > > > > On 14 August 2011 18:50, sagar pareek <sagarpar...@gmail.com> wrote: > > > > > > > > > > > > > Hashing > > > O(n+m) > > > > > On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro <dip10c...@gmail.com > >wrote: > > > > >> how about binary search of each element from array 1 on array 2? > > > > >> overall complexity : O(nlogn) > > > > >> On 14 August 2011 18:46, mohit verma <mohit89m...@gmail.com> wrote: > > > > >>> example: > > >>> array 1 :: 1 2 3 4 5 6 7 8 9 10 15 > > >>> array 2:: 23 34 56 13 "15" 57 432 348 > > > > >>> On Sun, Aug 14, 2011 at 6:44 PM, shady <sinv...@gmail.com> wrote: > > > > >>>> meaning ? what is a common element ? example ??????????????????????? > > > > >>>> On Sun, Aug 14, 2011 at 6:37 PM, mohit verma <mohit89m...@gmail.com > >wrote: > > > > >>>>> given two arrays : with all distinct elements but one element in > > >>>>> common. Find the common element in optimal time. > > > > >>>>> -- > > >>>>> ........................ > > >>>>> *MOHIT VERMA* > > > > >>>>> -- > > >>>>> You received this message because you are subscribed to the Google > > >>>>> Groups "Algorithm Geeks" group. > > >>>>> To post to this group, send email to algogeeks@googlegroups.com. > > >>>>> To unsubscribe from this group, send email to > > >>>>> algogeeks+unsubscr...@googlegroups.com. > > >>>>> For more options, visit this group at > > >>>>>http://groups.google.com/group/algogeeks?hl=en. > > > > >>>> -- > > >>>> You received this message because you are subscribed to the Google > > >>>> Groups "Algorithm Geeks" group. > > >>>> To post to this group, send email to algogeeks@googlegroups.com. > > >>>> To unsubscribe from this group, send email to > > >>>> algogeeks+unsubscr...@googlegroups.com. > > >>>> For more options, visit this group at > > >>>>http://groups.google.com/group/algogeeks?hl=en. > > > > >>> -- > > >>> ........................ > > >>> *MOHIT VERMA* > > > > >>> -- > > >>> You received this message because you are subscribed to the Google > Groups > > >>> "Algorithm Geeks" group. > > >>> To post to this group, send email to algogeeks@googlegroups.com. > > >>> To unsubscribe from this group, send email to > > >>> algogeeks+unsubscr...@googlegroups.com. > > >>> For more options, visit this group at > > >>>http://groups.google.com/group/algogeeks?hl=en. > > > > >> -- > > > > >> > ___________________________________________________________________________________________________________ > > > > >> Please do not print this e-mail until urgent requirement. Go Green!! > > >> Save Papers <=> Save Trees > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to algogeeks@googlegroups.com. > > >> To unsubscribe from this group, send email to > > >> algogeeks+unsubscr...@googlegroups.com. > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > ** > > > Regards > > > SAGAR PAREEK > > > COMPUTER SCIENCE AND ENGINEERING > > > NIT ALLAHABAD > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > > ___________________________________________________________________________________________________________ > > > > Please do not print this e-mail until urgent requirement. Go Green!! > > Save Papers <=> Save Trees > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- ___________________________________________________________________________________________________________ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers <=> Save Trees -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
