thanks guys. On Mon, Aug 15, 2011 at 1:12 PM, Nikhil Veliath <[email protected]> wrote:
> Dave tu mahan hai . . . . > ---------- Forwarded message ---------- > From: "Dipankar Patro" <[email protected]> > Date: 14 Aug 2011 23:27 > Subject: Re: [algogeeks] Re: array question > To: <[email protected]> > > @Dave nice algo. Really like it. > > So the whole complexity depends on the sorting. > > > On 14 August 2011 22:58, Dave <[email protected]> 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 <[email protected]> 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 <[email protected]> wrote: >> > >> > >> > >> > >> > >> > > Hashing >> > > O(n+m) >> > >> > > On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro <[email protected] >> >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 <[email protected]> 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 <[email protected]> wrote: >> > >> > >>>> meaning ? what is a common element ? example >> ??????????????????????? >> > >> > >>>> On Sun, Aug 14, 2011 at 6:37 PM, mohit verma < >> [email protected]>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 [email protected]. >> > >>>>> To unsubscribe from this group, send email to >> > >>>>> [email protected]. >> > >>>>> 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 [email protected]. >> > >>>> To unsubscribe from this group, send email to >> > >>>> [email protected]. >> > >>>> 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 [email protected]. >> > >>> To unsubscribe from this group, send email to >> > >>> [email protected]. >> > >>> 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 [email protected]. >> > >> To unsubscribe from this group, send email to >> > >> [email protected]. >> > >> 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 [email protected]. >> > > To unsubscribe from this group, send email to >> > > [email protected]. >> > > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
