this is how it works
list 1 : H1-5-5-5-5-5
list 2 : H2-4-4-4-4-4
now we need to return a list say list 3 as our answer which contains the sum
and length at most n+1 (in this case as m=n)
step 1 : we spent O(n) to simply conclude they are of same length
step 2:
list 3: 9-9-9-9-9-H3
(we
it doesn't matter
in that case
list 3 becomes: (step 2)
9-9-9-9-10-H3
after processing it becomes (step 3)
H3-1-0-0-0-0-0
On Tue, Feb 2, 2010 at 3:42 PM, Harish U harishs...@gmail.com wrote:
saurabh pleeease look at the list that i have mentioned carefully
.. second list must be
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
@saurabh :
so you scanned to find out that both lists are same : O(n) (agreed)
prepare list 3 in time O(n) (agreed)
process list 3 in time O(n) (*HOW ??*)
can you run through your method and show how you process list 3 in O(n)
using the below lists as input:
5-5-5-5-5-5-5-5-5-5 and
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,
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
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
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
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
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
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
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
12 matches
Mail list logo
