On 2010-8-25 20:25, Terence wrote:
1. Calculate the length of both list (A, B).
2. Find the position in the longer list corresponding to the head of
shorter list, and copy the previous digits to output list C.
(Or for simplicity, appending 0 to the shorter list so as to get
the same length as the longer one)
3. Add the two lists into list C without performing carry.
4. Perform carries. For each digit x in sum C, and the previous digit px.
a) if x < 9, no change to x and px;
b) if x > 9, x = x - 10, px = px + 1;
c) if x ==9, continue to next digit until you come to a digit x'
not equal to 9 (or the end of list)
if x' > 9, x' = x' - 10, px = px + 1, and change all
the 9's in between to 0.
else, keep all those digits untouched.
step 3 and 4 can be merged into one pass.
Some clarifications to step 4:
1) Pointer update:
Initially x point to the head of list C, and px point to a virtual
node with value 0.
(If carry to this node is performed, a node of value 1 is added to
the head of C)
After step 4.a, 4.b, both px and x pointed to the next node.
After step 4.c, px advanced to x' and x pointed to the next of x'.
2) Correctness.
The operation of step 4 (with above update procedure) ensures px < 9
before possible carry.
0. Initially, px = 0
1. After 4.a, px = x < 9
2. After 4.b, px = x - 10, while x is sum of 2 digits, so x <= 18 =>
px <= 8
3. After 4.c, if x' is not the tail of list, then x' != 9. px =
x'(x'<9) or px = x'-10(x'>9)
after update. Similar to above 2 cases, px < 9.
So after the pass of step 4, we've got the final result.
The key point behind the steps is taking groups of (99..9x) as a whole.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
