I see. I think I didnt get your algorithm earlier, still dont get it :) I think instead of foreach(bj in B), you just want to say j=1 and in "next bj", you meant j++ ? can you explain what you mean by "ck change to its neighbor in C", do you mean you move the index up? or down? Also is C is sorted - you say C has to be sorted in decreasing order, so I guess you are moving the index down.
On Sun, Nov 1, 2009 at 1:34 AM, daizi sheng <daizish...@gmail.com> wrote: > In the inner loop, either ck get decreased, or bj get increased, > but you know there are at moast n possible ck and n possible bj, so > the complexity > of the inner loop is at most O(n), plus the outer loop, the whole > complexity > is O(n^2) > > On Sun, Nov 1, 2009 at 4:32 PM, Arun <arunm...@gmail.com> wrote: > > This is O(n^3) because of the goto statement (effectively you have > replaced > > a loop with goto :) I think. > > Instead of neightbor in C, you can do a binary search. > > This is what I could think of but it doesnt meet the problem's requiremen > - > > O(nlgn): > > 1) O(n^2logn) with O(1) space:) > > Sort all 3 arrays. For each pair of a[i],b[j], binary search for > > (0-(a[i]+b[j])) in C to see if its present. > > 2) O(n^2) with O(n) space > > Same as above, but instead of binary search of 0-(a[1]+b[j]) on C, you > put > > all elements of C in a hash. > > There must be some variation of merge sort to do it in nlgn, but Im not > able > > to see it :) > > On Sun, Nov 1, 2009 at 12:39 AM, daizi sheng <daizish...@gmail.com> > wrote: > >> > >> with all arrays sorted firstly, if you enumerate ai, bj in ascedning > >> order, > >> ck will be sure in descending order. > >> > >> foreach(ai in A) > >> ck = largest element in C > >> foreach(bj in B) > >> AGAIN: > >> if(ai + bj + ck == 0) algorithm over > >> if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN > >> if(ai + bj + ck < 0) continue checking next bj > >> > >> > >> On Sun, Nov 1, 2009 at 3:10 PM, anilkumarmyla <anilkumarm...@gmail.com> > >> wrote: > >> > No matter whatever i could think of, I am unable to do better than N^3 > >> > > >> > @daizi sheng > >> > I don't get your algorithm > >> > "2. enumerate ai, bj both in ascending order," > >> > Will that really help ? In what way ? > >> > > >> > -- > >> > > >> > You received this message because you are subscribed to the Google > >> > Groups > >> > "Algorithm Geeks" group. > >> > To post to this group, send email to algoge...@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 algoge...@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 algoge...@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 algoge...@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 algoge...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
