Multiply Digit Strings
Problem
Two non-negative whole numbers are given as text, most significant digit first, and may be far too long to fit in a machine integer. Return their product, also as text. Converting the inputs to built-in numbers is not allowed, and the result must carry no leading zeros.
Examples
Input: a = "123", b = "456"
Output: "56088"Input: a = "9", b = "99"
Output: "891"
Why: the carry out of the last column adds a digitInput: a = "0", b = "52"
Output: "0"
Why: edge case, a zero factor must not produce a padded resultHints
0 / 3
Do the multiplication the way it is taught on paper, but notice that you never have to write out the intermediate rows separately.
The digit at position i of one number times the digit at position j of the other always lands in the same output column, whichever order you process the pairs in.
Reserve as many output slots as the two lengths added together. Add every digit product into the slot determined by its two positions, letting slots grow past nine for now. Afterwards sweep from the last slot to the first, carrying the tens part one slot to the left, then drop any leading zeros.
Solution
Each pair of digits contributes to a fixed output column, so all the products can be accumulated into a slot array before any carrying happens; that separation is what keeps the code short. A product of an i-digit and a j-digit number never needs more than i+j slots, which sizes the array up front. A single right-to-left sweep then normalises every slot to one digit, and stripping leading zeros finishes the job, with the zero factor handled up front so nothing is stripped away entirely. Time is O(i times j), and space is O(i + j).
def multiply_digits(a, b):
if a == "0" or b == "0":
return "0" # otherwise the sweep would strip everything
slots = [0] * (len(a) + len(b)) # a product never needs more columns than this
for i in range(len(a) - 1, -1, -1):
for j in range(len(b) - 1, -1, -1):
slots[i + j + 1] += int(a[i]) * int(b[j]) # the column is fixed by i and j
for k in range(len(slots) - 1, 0, -1):
slots[k - 1] += slots[k] // 10 # carry the tens leftwards
slots[k] %= 10
return "".join(str(d) for d in slots).lstrip("0")
print(multiply_digits("123", "456")) # -> 56088
print(multiply_digits("9", "99")) # -> 891
print(multiply_digits("0", "52")) # -> 0Stuck on the idea rather than the code? String Basics covers it.