the key observation is that your requirement for no space is nullified by
using the space in the resultant list.
so you scanned to find out that both lists are same : O(n)
prepare list 3 in time O(n)
process list 3 in time O(n)
current list 3 is the answer as list 4 is empty
total time O(n) as k is small
On Mon, Feb 1, 2010 at 11:19 PM, saurabh gupta <sgup...@gmail.com> wrote:
> 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
>>>>>>> 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<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.
