Re: [algogeeks] Add 2 long integers with digits represented by linked lists
The solution is essentially the same as Anurag's; Only that it would be simple to reverse both the lists So now the lists look like Num 1 = 123456 Num 2= 1234 Link-1-Link-2-Link-3-Link-4-Link5-Link6 head_num1 Link-1-Link-2-Link-3-Link-4 -head_num2 Now basically loop, and add the keys, remembering to take the carry ... and if there is carry in the last stage, then make an extra node. Regards 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.comalgogeeks%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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin Final Year Masters Student Dept Computer Science and Engineering Indian Institute of Technology Kanpur Kanpur - 208016 INDIA -- 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.
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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.comalgogeeks%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.comalgogeeks%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.
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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. 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. -- 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. -- 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. -- 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.
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
well, you may reverse them again :-) anyways, assume n m, since our result is again a new link list with size at most n+1. lets use this storage. We can use this storage to begin with. take 2 temp pointers and iterate till you reach the end of either one i.e. the smaller one. now say list 2 has length m, say temp pointer p1 is at position n-m in list 1. we have remaining space of n-m, create a new link list 4 which is list 1 reversed from position 1 to n-m. now sum of any 2 nodes is at most 18, start iterating from position n-m+1 (p1) in list 1 and position 1 in list 2. as you proceed start creating a reverse link list with the sums in each node i.e. list 1 = 4-7-8-1-6 list 2 = 2-3-4 list 3 = 10-4-10 list 4 = 7-4 now reverse list 3 with the following if no 9 save a carry over, sum carry over + number. list 3 becomes: 0-5-0 and carry 1. join 3 and 4 taking care of carry over to get (reversing 4 in the process) 4-8-0-5-0 This also assumes you can store integers 9 in a node which should be fine. 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.comwrote: 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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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.comwrote: 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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.
