Numbers as sequences of digits

Carrying, borrowing, and the boundary case that appears in every single one of these problems.

Key idea

The shape of digit arithmetic

When a number is given as an array of digits, arithmetic on it is done the way you would by hand: right to left, carrying into the next position.

You wrote this for linked lists in Unit 7, and the structure is identical. The only difference is that an array can be indexed backward directly, and that the result may need to grow at the front rather than the end.

The interesting part is where the carry stops, so here it is traced on two inputs, one that stops partway and one that never does.

1for digits in ([1, 2, 9], [9, 9]):2    index = len(digits) - 13    while index >= 0 and digits[index] == 9:4        print(f"{digits}: position {index} holds a 9, so it carries")5        index -= 16    if index >= 0:7        print(f"{digits}: position {index} absorbs the carry\n")8    else:9        print(f"{digits}: the carry ran off the front\n")

Only the second case needs the result to grow, and only an all-nines input produces it.

Key idea

Multiplication needs position arithmetic

Multiplying two digit arrays by hand produces one partial product per digit of the second number, each shifted. Doing it with an array means knowing exactly where each partial product lands.

The identity to remember: digit i of one number times digit j of the other contributes to positions i plus j and i plus j plus 1 of a result array indexed from the left. Deriving it on a two-by-two example takes a minute and removes all the guesswork.

1a = [3, 4]        # 34, most significant digit first2b = [2, 5]        # 253 4for i in range(len(a)):5    for j in range(len(b)):6        print(f"{a[i]} x {b[j]} = {a[i] * b[j]:>2}  ->  positions {i + j} and {i + j + 1}")

Where each pairwise product lands in a result array of length four.

Predict the output· 5 min

Predict the output: forgetting the grow case

This adds one to a digit array but returns the array without handling a carry past the front. Type the three values it prints.

Python

1def add_one_broken(digits):2    result = digits[:]3    index = len(result) - 14    while index >= 0:5        if result[index] < 9:6            result[index] += 17            return result8        result[index] = 09        index -= 110    return result11 12print(add_one_broken([1, 2, 3]), add_one_broken([1, 2, 9]), add_one_broken([9, 9]))

Printed output

Problem· 15 min

Plus One

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 30 min

Multiply Strings

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1for digits in ([1, 2, 9], [9, 9]):2 index = len(digits) - 13 while index >= 0 and digits[index] == 9:4 print(f"{digits}: position {index} holds a 9, so it carries")5 index -= 16 if index >= 0:7 print(f"{digits}: position {index} absorbs the carry\n")8 else:9 print(f"{digits}: the carry ran off the front\n")

1def add_one_broken(digits):2 result = digits[:]3 index = len(result) - 14 while index >= 0:5 if result[index] < 9:6 result[index] += 17 return result8 result[index] = 09 index -= 110 return result11 12print(add_one_broken([1, 2, 3]), add_one_broken([1, 2, 9]), add_one_broken([9, 9]))