Sorry for the mistake of addition vs subtraction. See my previous post
for some clarifications on the addition procedure.
The procedure of subtraction is similar.
To calculate C=A-B:
1. Compare A and B, (first compare length. If length is equal, compare
the digits from first to last).
If A = B, then output C = 0. (A list of single node 0, or an empty
list, depending on the format needed).
If A < B, then record the sign of C as minus, and swap A and B.
2. Find the position in A corresponding to the head of B, and copy the
previous digits of A to output list C.
(Or for simplicity, appending 0 to B so as to get the same length as A)
3. Subtract B from A without carry, get intermediate list C.
4. Perform carries on C. For each digit x in sum C, and the previous
digit px.(For the first digit x, px = 0)
a) if x > 0, no change to x and px, both px and x advanced to next
node.
b) if x < 0, x = x + 10, px = px - 1, both px and x advanced to
next node.
c) if x = 0, continue to next digit until you come to a digit x'
not equal to 0 (or the end of list)
if x' < 0, x' = x' + 10, px = px - 1, and change all
the 0's in between to 9.
else, keep all those digits untouched.
Advance px to x' and x to the next of x'.
5. Remove the initial 0s until C begins with non-zero digits.
On 2010-8-25 23:45, Raj N wrote:
@Terence: It is subtraction of 2 lists and not addition. N for your
logic of addition for x>9 you add px+1 and after that if it becomes >
9 how do you know the previous of it as you've moved the previous
pointer?
Can someone comment on my logic ?
On Wed, Aug 25, 2010 at 9:10 PM, Raj N <rajn...@gmail.com
<mailto:rajn...@gmail.com>> wrote:
They've mentioned that they're large lists. What if it is a 15
digit number? Its not efficient then.
On Wed, Aug 25, 2010 at 8:29 PM, Sathaiah Dontula
<don.sat...@gmail.com <mailto:don.sat...@gmail.com>> wrote:
@Raj,
How about doing like below ?
Convert A to base 10 number, numA
Convert B to base 10 number, numB,
Then take the difference numC = abs(numA - numB),
Then convert numC to linked list with the digits
any comments ?, overflow condition is the problem here.
Thanks & regards,
Sathaiah Dontula
On Wed, Aug 25, 2010 at 3:24 PM, Raj N <rajn...@gmail.com
<mailto:rajn...@gmail.com>> wrote:
Input : Two large singly linked lists representing numbers
with most
significant digit as head and least significant as last node.
Output: Difference between the numbers as a third linked
list with
Most significant digit as the head.
Eg:
---
Input:
A = 5->4->2->0->0->9->0->0
B = 1->9->9
Output:
C = 5->4->2->0->0->7->0->1
Required complexity :
O(n)
Constraint:
Reversing linked list is NOT allowed
--
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
<mailto:algogeeks@googlegroups.com>.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
<mailto: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
algogeeks@googlegroups.com <mailto:algogeeks@googlegroups.com>.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
<mailto: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.
--
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.
