0370MediumLinked ListMathStack

Add Two Digit Strips

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two whole numbers reach you as digit strips. A strip is a list of single digits written the way you would read the number off a page, most significant digit first, so [3, 0, 6] stands for three hundred and six. A strip always holds at least one digit, and the only strip that may open with a 0 is the single-digit strip [0].

Return the sum of the two numbers as a strip in the same format: most significant digit first, and with no leading zeros.

The strips stand in for singly linked lists, which can only be walked from the most significant digit onwards. Reach the low-order digits with a stack or by reversing rather than pasting the digits together into one integer value.

Examples

Example 1

Input: first = [4,5,6], second = [7,8]
Output: [5, 3, 4]

The strips stand for 456 and 78. Their sum is 534, written as the strip [5,3,4].

Example 2

Input: first = [9,9], second = [1]
Output: [1, 0, 0]

99 plus 1 is 100, so the answer strip is one digit longer than either input strip.

Example 3

Input: first = [0], second = [7]
Output: [7]

0 plus 7 is 7, a single-digit strip.

Example 4

Input: first = [3,0,6], second = [1,9,4]
Output: [5, 0, 0]

306 plus 194 is 500, written as [5,0,0].

Constraints

1 <= first.length, second.length <= 100
0 <= first[i], second[i] <= 9
Neither strip has a leading zero, except for the strip [0] itself.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def add_two_numbers(first: list[int], second: list[int]) -> list[int]:

Java

public int[] addTwoNumbers(int[] first, int[] second)

The intended approach

Time O(n + m)Space O(n + m) for the two stacks and the returned strip

Copy each strip into a stack so that popping hands back the least significant digit first. Pop from both stacks together, add whatever the shorter strip no longer supplies as nothing, keep a carry across rounds, and collect the digits produced. Because the digits come out lowest first, reverse the collection at the end, and drop any leading zero the collection picked up.

Pythonentry point: add_two_numbers

def add_two_numbers(first, second):
    # Push both strips onto stacks so they can be consumed from their least
    # significant ends, then carry upward and reverse the collected digits.
    # Time O(n + m), space O(n + m) for the stacks and the answer.
    a = list(first)
    b = list(second)
    out = []
    carry = 0
    while a or b or carry:
        total = carry
        if a:
            total += a.pop()
        if b:
            total += b.pop()
        out.append(total % 10)
        carry = total // 10
    out.reverse()
    while len(out) > 1 and out[0] == 0:
        out.pop(0)
    return out

The obvious version

Pad both strips on the left to a common width with one spare column, add the two columns at each position with no carrying at all, then repeatedly sweep right to left moving any column above nine into its neighbour until every column is a single digit, and trim leading zeros.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_add_two_numbers(first, second):
    width = max(len(first), len(second)) + 1
    a = [0] * (width - len(first)) + list(first)
    b = [0] * (width - len(second)) + list(second)
    raw = [a[k] + b[k] for k in range(width)]
    changed = True
    while changed:
        changed = False
        for k in range(width - 1, 0, -1):
            if raw[k] > 9:
                raw[k] -= 10
                raw[k - 1] += 1
                changed = True
    start = 0
    while start < width - 1 and raw[start] == 0:
        start += 1
    return raw[start:]

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in