1393. Count the Carries
Two non-negative integers are given as decimal strings. Print how many carries the schoolbook addition produces.
``` 555 each column is 5 + 5 = 10, so every column carries + 555 ----- answer 3
1 the units column is 1 + 9 = 10, which carries, and the + 9 carry into the tens column makes 1 with nothing to add ----- answer 1 ```
A carry happens in a column when the two digits plus the incoming carry reach
10 or more. A carry out of the leftmost column counts too, as in 9 + 1, where
the single column carries and the result gains a digit.
## What most people try first
Add the numbers, then compare lengths, or try to spot carries in the result.
Neither works: the length changes at most once however many carries happen, and
the result does not record where they occurred. The numbers are also far too
large to hold in any fixed width type, with up to 10^5 digits each.
## One scan from the right
i = last index of a, j = last index of b, carry = 0, count = 0
while i >= 0 or j >= 0:
s = carry + (digit of a at i, or 0) + (digit of b at j, or 0)
if s >= 10: carry = 1, count = count + 1
else: carry = 0
step i and j left
The loop must continue while either index is still in range, not while both
are, or a carry propagating into the longer number's remaining digits is
missed. The declared test 999999999999999999999999 + 1 is exactly that: the
answer is 24, and a loop that stops at the shorter number reports 1.
Note that the loop as written does not need an extra round after both strings are exhausted. A carry out of the leftmost column is already counted in the column that produced it.
## A second way to see the answer, which is how these outputs were checked
Every carry takes 10 out of one column and puts 1 into the next, so it reduces the total digit sum by exactly 9. That gives a formula with no scan in it:
carries = ( digitsum(a) + digitsum(b) - digitsum(a + b) ) / 9
For 555 + 555 = 1110: 15 + 15 - 3 = 27, and 27 / 9 = 3. This identity is
Kummer's theorem in the decimal case, and it is why every expected output in
this problem has been computed twice by unrelated means.
## Overflow
Nothing here can overflow. Each string has at most 10^5 digits, so a digit
sum is at most 9 * 10^5 and the carry count is at most 10^5. Both are far
inside a signed 32-bit integer, whose limit is 2147483647. The numbers
themselves are never converted to integers at all, which is the point: they
would need 332 bits.
## Cost
O(max(len(a), len(b))).
Constraints - Each number has between 1 and 100000 digits. - Neither has a leading zero, except that zero is written `0`. - A carry out of the leftmost column counts.
Input
Two lines, each a non-negative integer written in decimal with no leading zeros, except that zero itself is written 0.
Output
Print the number of carries the schoolbook addition of the two numbers produces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.