Carry chains
In a ripple-carry adder each digit waits for the carry from its neighbour on the right, and the time of an addition is set by the longest chain of carries; this is covered in the basic course chapter “The machine does arithmetic”. Big-number arithmetic adds the same way, only with millions of digits instead of 64.
Two natural numbers are given in decimal notation. Add them in a column and count how many times a carry into the next digit occurred and how long the longest chain of carries is: how many digits in a row passed a one to the next. For example, adding 999,999 and 1 gives six carries, all in a row. One of the tests is the first million digits of π and the first million digits of e.
Input
Two lines, each holding a natural number without leading zeros, at most 10⁶ digits long. The lengths of the numbers may differ.
Output
Two numbers separated by a space: the number of carries and the length of the longest chain of carries.
Examples
Example 1
758 467
3 3
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A carry occurs when the sum of the two digits of a position and the incoming carry is at least 10. What happens in a position where the digits add up to exactly 9?
2Hint 2
Turning the strings into numbers and adding them with built-in arithmetic is useless: the sum does not say where the carries were. You need to walk the digits from right to left, as in column addition, and keep the carry in a variable.
3The idea
This is big-number addition in base 10, except that instead of the digits of the sum we are interested in the carry. Go from the lowest digit to the highest: s = ai + bi + carry, and the new carry is 1 if s ≥ 10. Count the carries and the length of the current run: a carry extends it, its absence resets it to zero.
4Walkthrough
Reverse the strings so that index 0 is the lowest digit. If one number is shorter, the missing digits are zeros. A carry out of the highest digit counts too: 999,999 + 1 has six, and the last creates the seventh digit of the answer. One pass, with memory only for the input.
What comes out on π and e is curious. There are 500,105 carries per million digits, almost exactly half, as with random digits: a carry occurs for a sum from 10 to 18 (45 pairs out of 100) and for a sum of 9 with a carry from below (another 10 pairs), and on average that is one half. The longest chain is 21. For random digits a chain continues with probability 0.55 (a sum of 9 or more), and the longest out of a million is expected to be about log1/0.55(450,000) ≈ 22.
4+Solution
5Complexity
O(n) time, where n is the length of the longer number, and O(n) memory for the strings themselves.
6Common mistakes
- Only the pair of digits. The condition “ai + bi ≥ 10” misses the positions where the digits add up to 9 and a one came from below. On 999 + 1 it gives one carry instead of three.
- Different lengths. A chain can run past the end of the shorter number: 999,999 + 1.
- Slow input. A million digits must be read in one go, not character by character; in Go, through buffered input.