nope,
if both lists are of same length list 4 is not required and you save time to
deal with list 4
so, you have list 3 only
time reqd is O(3n)
3 passes approximately
On Mon, Feb 1, 2010 at 11:24 AM, Algoose Chase <harishp...@gmail.com> wrote:
> Thats true ! , The purpose is to add very long integers such that we cant
> use premative data types to represent them.
>
> The point I was trying to prove is : you would need to go through multiple
> passes through the list(essentially to propagate carry) when you have
> conditions like No Reversing the original lists and no recursion and no to
> any extra memory usage.
>
> @ saurabh: Hope you have not considered the worst case before generalizing
> the running time to 2n+m .
>
> lets assume the 2 lists are of same size so n = m.This eliminates the need
> to find out m or to create list 4
> and lets assume the linked list are 5->5->5->5->5->5->5->5->5->5 and
>
> 4->4->4->4->4->4->4->4->4->5
> Only thing is you need to create list 3 (as u have mentioned) . Now its not
> possible to add the 2 lists through a single pass from left to right . This
> would need n passes on a linked list of size n making the running time n^2.
>
>
>
> On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta <sgup...@gmail.com> wrote:
>
>> this defeats the purpose,
>> they are stored in linked list because they cannot be stored in a given
>> type.
>>
>>
>>
>> On Thu, Jan 28, 2010 at 3:25 AM, Deva R <r.deva...@gmail.com> wrote:
>>
>>> i faced this qn in ********* interview.
>>>
>>> best soln i could give was:
>>>
>>> - traverse each list and derive both the numbers.. something like below
>>>
>>> node = list->head;
>>> i=1; value =0;
>>> while (node)
>>> { value = (node->data)*i +value;
>>> i*=10;
>>> node = node->next;
>>> }
>>>
>>> - add both the numbers. u can either return the number or form a new list
>>> and return.
>>>
>>> i gave the code.. and its o(m+n), for lists of size m,n.
>>>
>>> -Deva
>>>
>>>
>>>
>>> On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta <sgup...@gmail.com>wrote:
>>>
>>>> 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 algogeeks@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<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.
