1347. Multiply Two Numbers Too Big to Hold
Two non-negative integers are given as strings of up to 2000 digits. Print their product.
Long multiplication, written down precisely. The key observation makes the whole thing fall out:
digit i of a, times digit j of b, contributes to position i + j
counting positions from the RIGHT of each number. So allocate an array of
len(a) + len(b) slots, add every pairwise product into its slot without
worrying about carries, and normalise once at the end.
Letting the slots grow first and carrying afterwards is what keeps the code
short. Each slot holds at most 2000 * 81, well inside a 32-bit integer, so
nothing overflows before the carry pass.
Then sweep from the right: keep slot % 10, carry slot / 10 into the next.
Two traps. The result may be shorter than len(a) + len(b), so leading zeros
must be stripped, but not all of them: a product of zero must still print 0
rather than an empty line. And if either input is 0 the whole product is 0,
which the strip handles only if it is written to leave one digit behind.
Constraints - Each number has between 1 and 2000 digits. - Neither has a leading zero unless it is exactly `0`.
Input
Two lines, each containing a non-negative integer with no leading zeros other than the number 0 itself.
Output
Print their product, with no leading zeros.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.