Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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 haven't used any extra space simply utilized the space where we store
the answer)
(not the pointers in lis3 they are in the 'opposite' sense)
plus we haven't touched 1 or 2
step 3:
list 3: H3-9-9-9-9-9
this is the answer.
This is actually a special case.
On Tue, Feb 2, 2010 at 10:40 AM, Algoose Chase harishp...@gmail.com wrote:
@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
4-4-4-4-4-4-4-4-4-5
hope you know the constraints : you cant reverse original list. and you
cant use recursion. and you need to traverse the list LEFT TO RIGHT to
satisfy the first 2 conditions.
Yes , I agree these lists takes O(n) time: list 1 = 4-7-8-1-6
list 2 =
2-3-4
but not in all cases.
I agree that for most cases(except the wild ones) the running time must be
O(n) only but you certainly need multiple passes depending upon the input.
Hope I am clear !
On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta sgup...@gmail.com wrote:
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.comwrote:
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.comwrote:
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.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta sgup...@gmail.comwrote:
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
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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 H2-4-4-4-4-5 and not H2-4-4-4-4-4.
Its straight forward to do the job with the list you have done with so far.
On Tue, Feb 2, 2010 at 12:22 PM, saurabh gupta sgup...@gmail.com wrote:
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 haven't used any extra space simply utilized the space where we store
the answer)
(not the pointers in lis3 they are in the 'opposite' sense)
plus we haven't touched 1 or 2
step 3:
list 3: H3-9-9-9-9-9
this is the answer.
This is actually a special case.
On Tue, Feb 2, 2010 at 10:40 AM, Algoose Chase harishp...@gmail.comwrote:
@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
4-4-4-4-4-4-4-4-4-5
hope you know the constraints : you cant reverse original list. and you
cant use recursion. and you need to traverse the list LEFT TO RIGHT to
satisfy the first 2 conditions.
Yes , I agree these lists takes O(n) time: list 1 = 4-7-8-1-6
list 2 =
2-3-4
but not in all cases.
I agree that for most cases(except the wild ones) the running time must
be O(n) only but you certainly need multiple passes depending upon the
input.
Hope I am clear !
On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta sgup...@gmail.comwrote:
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.comwrote:
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.comwrote:
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.comwrote:
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.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta
sgup...@gmail.comwrote:
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
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta sgup...@gmail.comwrote:
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 algogeeks@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
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
@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
4-4-4-4-4-4-4-4-4-5
hope you know the constraints : you cant reverse original list. and you cant
use recursion. and you need to traverse the list LEFT TO RIGHT to satisfy
the first 2 conditions.
Yes , I agree these lists takes O(n) time: list 1 = 4-7-8-1-6
list 2 = 2-3-4
but not in all cases.
I agree that for most cases(except the wild ones) the running time must be
O(n) only but you certainly need multiple passes depending upon the input.
Hope I am clear !
On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta sgup...@gmail.com wrote:
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.comwrote:
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.comwrote:
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.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta sgup...@gmail.comwrote:
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
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.
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
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.
