Stadium Gate Tallies
A stadium counts fans at its north and south gates with old counters that store a number as a chain of digits, ones digit first. So 4,071 fans is stored as 1 → 7 → 0 → 4. The counters were built to grow without limit, so a tally can be far longer than any built-in integer type can hold.
At the end of the night the stadium needs the total for both gates, stored the same way.
Your task
Write addTallies(north, south). Each argument is a non-empty linked list of digits (0 to 9), ones digit first. Return a linked list holding the sum, in the same format.
The lists may have different lengths. Neither has extra zeros at the end of the chain (its highest digit), except the number 0 itself, which is [0]. The result must follow the same rule.
addTallies(north: ListNode, south: ListNode) → ListNode
Examples
north = [1, 7, 0, 4] south = [9, 5, 6]
[0, 3, 7, 4]
That is 4,071 + 659 = 4,730. Ones: 1 + 9 = 10, write 0 carry 1. Tens: 7 + 5 + 1 = 13, write 3 carry 1. Hundreds: 0 + 6 + 1 = 7. Thousands: 4. Read ones first: 0, 3, 7, 4.
north = [8, 9] south = [4]
[2, 0, 1]
98 + 4 = 102. 8 + 4 = 12, write 2 carry 1. 9 + 1 = 10, write 0 carry 1. Both lists are finished but a carry is left, so it becomes a new digit, 1.
Constraints
- 1 ≤ length of each list ≤ 100
- 0 ≤ each digit ≤ 9
- Numbers can have up to 100 digits, so do not convert them to built-in numbers.
Start with brute force
Turn each chain into a number, add the two numbers, and turn the result back into a chain.
That breaks as soon as a tally passes about 16 digits: JavaScript numbers lose precision beyond 9,007,199,254,740,991, and many languages overflow at 64 bits. With up to 100 digits the answer would be wrong. Python's integers grow without limit, so there it happens to work, but it skips the skill this problem is about. Adding digit by digit works for any length, in any language.
Hints
0 of 4 shown- Hint 1
Add 98 + 4 on paper. Which digit do you start with, and which way do you move?
- Hint 2
Paper addition starts at the ones and moves left, passing a carry along. The lists are stored ones digit first, so walking the chain forwards is exactly the paper order.
- Hint 3
At each position you add three things: a digit from each list (or 0 if that list has run out) and the carry. What happens when both lists end but the carry is still 1?
- Hint 4
Walk both lists together with a
carrystarting at 0. While either list has nodes orcarryis not 0:sum = digitA + digitB + carry, append a node withsum % 10, setcarry = floor(sum / 10). Build the result with a dummy head and a tail pointer.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Storing the ones digit first is a gift: walking the chain forwards is the same order you use for addition on paper. So you just do paper addition, one node at a time, carrying as you go.
Trace 1 → 7 → 0 → 4 plus 9 → 5 → 6:
- 1 + 9 + carry 0 = 10. Write 0, carry 1.
- 7 + 5 + 1 = 13. Write 3, carry 1.
- 0 + 6 + 1 = 7. Write 7, carry 0.
- The south list is done, so its digit counts as 0. 4 + 0 + 0 = 4. Write 4.
- Both lists are done and the carry is 0. Stop. Result:
0 → 3 → 7 → 4, which is 4,730.
The loop condition includes carry. Without it, 98 + 4 would stop at 2 → 0 and lose the final 1. That missing last carry is the classic bug in this problem.
function addTallies(north, south) {
const dummy = new ListNode(0, null);
let tail = dummy;
let carry = 0;
while (north !== null || south !== null || carry !== 0) {
let sum = carry;
if (north !== null) { sum += north.val; north = north.next; }
if (south !== null) { sum += south.val; south = south.next; }
tail.next = new ListNode(sum % 10, null);
tail = tail.next;
carry = Math.floor(sum / 10);
}
return dummy.next;
}def add_tallies(north, south):
dummy = ListNode(0)
tail = dummy
carry = 0
while north is not None or south is not None or carry:
total = carry
if north is not None:
total += north.val
north = north.next
if south is not None:
total += south.val
south = south.next
tail.next = ListNode(total % 10)
tail = tail.next
carry = total // 10
return dummy.nextRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.