Math and Geometry
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.
Why it works
The case that appears in all of these
A carry out of the leftmost position means the result is longer than the input. Every digit problem in this family has that case and it is the one most often forgotten, because it only fires on inputs made entirely of the largest digit.
Test with all nines. It is one input, it takes five seconds, and it catches the single most common failure in this whole unit.
Gotcha
Copy before modifying
Writing into the input list changes the caller's data. Some problems permit that and most do not say, and a function that silently mutates its argument is a genuine defect.
Copy at the top with a slice. It is one line and it removes an entire class of surprise, which matters more here than the negligible cost.
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.
Why it works
Add into the positions, never assign
Two of the four pairs above land on positions 1 and 2. That is not a special case, it is the normal situation: every position except the two ends receives more than one product.
So each pair adds to whatever is already sitting in those positions rather than overwriting it, and the running value at a position can exceed nine while the loop is still going. Splitting it into a kept digit and a carry is the last step, not something that has to hold after every pair.
Tip
Why the result array is exactly that long
Two numbers of m and n digits multiply to a result of at most m plus n digits, and at least m plus n minus 1. So allocating m plus n is always enough and at most one leading zero needs stripping.
Knowing that bound up front means no resizing and no appending, which is what keeps the index arithmetic simple. Working out the size of the answer before allocating is worth doing in every problem of this kind.
Edge cases
Zero, and the leading-zero strip
Multiplying by zero produces an array of nothing but zeros, and a strip loop that removes every leading zero would leave an empty array rather than a single zero. Guard the whole thing with an early return when either input is zero, and give the strip loop a condition that refuses to shorten the result below one digit.
Having two independent defenses against the same case is not redundant here. The early return also avoids doing the work at all, and the loop condition protects against any other path that ends up producing zeros.
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.
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.
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.