step 1 is n not m which makes it O(3n) On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta <sgup...@gmail.com> wrote:
> its not exponential > time to find out m = m > time to create list 3 = m > time to create list 4 = n-m > time to come up with proper added list (list 3 modification) = m > time to merge list 3 and list 4 = n-m > > total time = 2n+m > > except step 1 all are reversals with approximately same constant and > constant for step 1 is smaller > so one can say > > O(2n+m) > > > On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia <abhati...@gmail.com>wrote: > >> If that is the representation, then the lists have to be reversed. >> Otherwise the time goes up exponentially. >> >> On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase <harishp...@gmail.com> >> wrote: >> > Condition: >> > Can we do it keeping the original lists intact ? ie without reversing >> it. >> > I mean , No recursion & no Reversing ... is it possible ? >> > >> > @kumar : >> > 15234 is represented as 1->5->2->3->4 >> > >> > On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta <sgup...@gmail.com> >> wrote: >> >> >> >> perhaps you mean, >> >> reverse each link list O(n+m). >> >> then sum each node with carryover maintained. >> >> >> >> On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia <abhati...@gmail.com> >> >> wrote: >> >>> >> >>> Let us take an example - >> >>> >> >>> Num 1 = 123456 >> >>> Num 2= 1234 >> >>> Link-1->Link-2->Link-3->Link-4->Link5->Link6 >> >>> Link-1->Link-2->Link-3->Link-4 >> >>> >> >>> Add nodes into linkedlist 1 till either one of the list is not null. >> >>> Make sure you process the carry in each iteration. >> >>> >> >>> >> >>> --AB >> >>> >> >>> >> >>> On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase <harishp...@gmail.com> >> >>> wrote: >> >>> > conditions: >> >>> > NO extra memory (@ stack or Heap) at all. No recursion. >> >>> > >> >>> > Any body has got any hint about how to get this done ? >> >>> > >> >>> > >> >>> > >> >>> > -- >> >>> > 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. >> >>> > To unsubscribe from this group, send email to >> >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >> >>> To unsubscribe from this group, send email to >> >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >> >> To unsubscribe from this group, send email to >> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. 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.
