@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.
