@dave: sorry I overlooked the constraint "u cannot modify the array" space is mandatory then.
On Aug 23, 12:07 pm, darklord <darklord....@gmail.com> wrote: > mofified array will be > C[0]=1 C[1]=2 C[2]=5 C[3]=8 C[4]=10 C[5]=20 > > @saurabh: obviously it does!!!!! > @Dave: no need of extra space also.... u can use quicksort. I think if > u r using extra space, U can do it in linear time using radixsort > (correct me if I'm wrong). > > On Aug 23, 11:44 am, Raghavan <its...@gmail.com> wrote: > > > > > > > > > A[0] = 10 A[1] = 2 A[2] = 5 > > A[3] = 1 A[4] = 8 A[5] = 20 > > > Triplet 10,5,8 is triangular. > > > Dave, do your solution do it? > > > On Tue, Aug 23, 2011 at 11:55 AM, Amol Sharma <amolsharm...@gmail.com>wrote: > > > > +1 for dave's solution.....i will also do the same > > > -- > > > > Amol Sharma > > > Third Year Student > > > Computer Science and Engineering > > > MNNIT Allahabad > > > <http://gplus.to/amolsharma99> > > > <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99> > > > > On Tue, Aug 23, 2011 at 11:25 AM, Dave <dave_and_da...@juno.com> wrote: > > > >> @Saurabh: If you can use O(n) extra space, make a copy of the array > > >> and sort it: O(n log n). Then, if there is a solution, there will be a > > >> solution of the form (a[i], a[i+1], a[i+2]), where 0 <= i < n-2, > > >> which can be checked with a simple for loop: O(n). Thus, the > > >> complexity is O(n log n). > > > >> Dave > > > >> On Aug 23, 12:04 am, saurabh agrawal <saurabh...@gmail.com> wrote: > > >> > Given an array, find out whether there exists a triplet which can form > > >> sides > > >> > of triangle. > > >> > You are not allowed to modify the array. > > > >> > PLease dont give o(n^3) solution > > > >> > there exists a solution with nlog(n) i think > > > >> -- > > >> 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. > > > -- > > Thanks and Regards, > > Raghavan KL -- 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.
