Column Addition with Carry

Column Addition with Carry

The grade-school addition algorithm, where you line up two numbers by their least significant digit, add column by column from right to left, and carry any overflow into the next column, translates almost directly into code. The challenge is expressing that pattern cleanly when numbers are represented as linked lists, reversed strings, or ordinary strings, while correctly handling unequal lengths and a final carry.

The Core Algorithm

At each digit position you compute a local sum: the digit from the first number, plus the digit from the second number, plus whatever carry came in from the previous column. The result digit for this column is total % 10. The carry into the next column is total // 10, which is either 0 or 1 for single-digit inputs.

The loop condition while l1 or l2 or carry is the key to handling three edge cases in a single check. It continues as long as there are more digits in either number, or there is a pending carry that has not yet been written out. If you used while l1 and l2 you would need separate logic for unequal lengths and for a final carry like the one that turns 99 + 1 into 100.

Walked Example: Adding 342 and 465 as Linked Lists

Consider LeetCode 2. Add Two Numbers, which stores integers in reverse order, so 342 is stored as 2 -> 4 -> 3. This means the head of each list is already the least significant digit, so no reversal is needed before processing.

Adding 342 + 465:

• Column 1 (ones): 2 + 5 + 0 (carry) = 7. Write 7, carry = 0.
• Column 2 (tens): 4 + 6 + 0 = 10. Write 0, carry = 1.
• Column 3 (hundreds): 3 + 4 + 1 = 8. Write 8, carry = 0.

Result list: 7 -> 0 -> 8, which represents 807 = 342 + 465. Correct.

Now consider 995 + 5, stored as 5 -> 9 -> 9 and 5:

• Column 1: 5 + 5 + 0 = 10. Write 0, carry = 1.
• Column 2: 9 + 0 + 1 = 10. Write 0, carry = 1. (l2 is exhausted but carry is not.)
• Column 3: 9 + 0 + 1 = 10. Write 0, carry = 1. (l1 is exhausted but carry is not.)
• Column 4: 0 + 0 + 1 = 1. Write 1, carry = 0.

Result: 0 -> 0 -> 0 -> 1, representing 1000 = 995 + 5. The final carry created an extra digit, which the or carry part of the while condition handled automatically.

Code for Add Two Numbers

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def add_two_numbers(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    carry = 0

    while l1 or l2 or carry:
        val = carry
        if l1:
            val += l1.val
            l1 = l1.next
        if l2:
            val += l2.val
            l2 = l2.next
        carry, digit = divmod(val, 10)
        curr.next = ListNode(digit)
        curr = curr.next

    return dummy.next

The dummy head node means the first result digit gets created the same way as every subsequent digit, curr.next = ListNode(digit), with no special case for the list being empty. At the end, dummy.next is the head of the result list.

Python's divmod(val, 10) returns (val // 10, val % 10), which is a concise way to split the carry and the digit in one line.

The String Addition Variant

LeetCode 415. Add Strings gives two non-negative integers as strings and asks you to add them without converting to integers. The numbers are stored in the natural order (most significant digit first), so you process from the right end using two index pointers.

def add_strings(num1, num2):
    i, j = len(num1) - 1, len(num2) - 1
    carry = 0
    result = []

    while i >= 0 or j >= 0 or carry:
        digit1 = int(num1[i]) if i >= 0 else 0
        digit2 = int(num2[j]) if j >= 0 else 0
        total = digit1 + digit2 + carry
        carry, digit = divmod(total, 10)
        result.append(str(digit))
        i -= 1
        j -= 1

    return "".join(reversed(result))

Because we append digits from least significant to most significant, we reverse result at the end. Alternatively, you can insert at position 0 each time, but that makes the overall algorithm $O(n^2)$ due to repeated string shifts. Appending and reversing once at the end is $O(n)$.

The structure of this loop is identical to the linked list version. The only differences are syntactic: index arithmetic instead of node.next, and int(char) to extract digit values.

The Multiply Strings Variant

With LeetCode 43. Multiply Strings, the task is to multiply two non-negative integers given as strings. The key insight is that the digit at position i in num1 and the digit at position j in num2 contributes to position i + j in the result (with carry potentially going to i + j - 1 if you index from the right, or i + j + 1 if you index from the left).

def multiply(num1, num2):
    m, n = len(num1), len(num2)
    pos = [0] * (m + n)  # result can have at most m + n digits

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = int(num1[i]) * int(num2[j])
            p1, p2 = i + j, i + j + 1  # p2 is the current digit position
            total = mul + pos[p2]
            pos[p2] = total % 10
            pos[p1] += total // 10  # carry propagates to p1

    # Convert to string, strip leading zeros
    result = "".join(str(d) for d in pos).lstrip("0")
    return result if result else "0"

The outer loops iterate from the least significant digit inward (m-1 down to 0 and n-1 down to 0). pos[p2] holds the running digit at column i + j + 1, and pos[p1] accumulates the carry into column i + j. After all multiplications are done, the pos array holds the final digits, and you just strip leading zeros.

This is the same carry-propagation idea from column addition, extended to handle partial products. Each column can accumulate contributions from multiple digit pairs before carries are resolved.

Complexity

For Add Two Numbers and Add Strings, the time complexity is $O(\max(m, n))$ where m and n are the lengths of the two inputs. Each digit is visited once. Space is $O(\max(m, n))$ for the output.

For Multiply Strings, the time complexity is $O(m \cdot n)$ due to the nested loops over all digit pairs. Space is $O(m + n)$ for the result array.

Recognizing this pattern

You're probably looking at column addition with carry when:

• The inputs are digit sequences too large for a 64-bit integer: strings, linked lists, or arrays of digits.
• The problem explicitly bans converting to integer ("do not convert the inputs to integer directly").
• You're asked to add, subtract, multiply, or compare numbers represented as strings or linked lists.
• The base is fixed (binary, decimal, or hex) and the digits arrive least- or most-significant-first.

Common templates:

• Linked-list digit addition: walk both lists with a while a or b or carry loop, build a new list. Example: Add Two Numbers.
• String addition, least-significant first: two pointers walking from the end, output digits, reverse at the end. Example: Add Strings.
• Binary or arbitrary-base addition: same loop with a different modulus and digit alphabet. Example: Add Binary.
• Grade-school long multiplication: for each pair (i, j), accumulate into position i + j + 1, then resolve carries in one pass. Example: Multiply Strings.