Problem overview
The method multiply gets two non-negative whole numbers as strings, num1 and num2, each with up to 1,000 digits. It returns their product, also as a string, with no zeros in front. A product of 0 is "0". The statement asks you to work with the digits rather than convert a whole string to a number, and to run in O(m · n) time, where m and n are the lengths of the strings.
For "25" and "16" the answer is "400". For "999" and "99" it is "98901", which has 5 digits, as many as the two inputs together. For "0" and "8317" it is "0".
Approach: long multiplication on paper
School multiplication pairs every digit of one number with every digit of the other, and each pair contributes to a column of the answer. Two digits multiply to at most 81. A product with m and n digits has at most m + n digits (99 times 99 is 9801), so a list of m + n zeros can hold the whole answer.
Number the answer's positions from the left, starting at 0. The digits num1[i] and num2[j] have place values that add up, and their product lands at position i + j + 1, with its tens carried into position i + j. For 25 times 16 the last digits are at i = 1 and j = 1, and 5 times 6 is 30, so the 0 stays in position 3 (the ones) and the 3 carries into position 2 (the tens).
Going through the pairs from the last digits to the first, as on paper, gives this state of the list after each pair, for "25" times "16":
i=1 j=1: product 30 [0, 0, 3, 0]
i=1 j=0: product 5 [0, 0, 8, 0]
i=0 j=1: product 12 [0, 2, 0, 0]
i=0 j=0: product 2 [0, 4, 0, 0]
The list ends as [0, 4, 0, 0]. The leading 0 is skipped, and the answer is "400".
Step by step
- Store the lengths with
m, n = len(num1), len(num2). Python assigns the values on the right to the names on the left in order. - Create
digitsas[0] * (m + n).digits[k]holds the answer's digit at positionkfrom the left. Some leading positions may stay 0. - Loop over
num1from the last digit to the first withrange(m - 1, -1, -1). The stop value is left out of a range, so-1includes index 0. - Loop over
num2the same way withj. Together, the loops pair each digit of one number with each digit of the other:m · npairs. - Multiply the two digits with
int(num1[i]) * int(num2[j]). Only one character is converted at a time; the strings stay strings. - Add the product to what is at position
i + j + 1intotal. This is the key line. Earlier pairs may have left a carry or a partial sum there. - Keep the ones digit of
totalin that position:total % 10. - Carry the rest left by adding
total // 10todigits[i + j]. That position can briefly pass 9. A later pair uses it as its owni + j + 1spot, adds to it and splits it again. - Skip the leading zeros. After the loops,
startbegins at 0. - Advance
startwhilestart < m + n - 1anddigits[start]is 0. The loop stops before the last position, so a product of 0 keeps one digit. - Add 1 to
startin the loop body. - Join the rest into a string with
"".join(str(d) for d in digits[start:]).
The solution in Python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
m, n = len(num1), len(num2)
digits = [0] * (m + n)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
product = int(num1[i]) * int(num2[j])
total = product + digits[i + j + 1]
digits[i + j + 1] = total % 10
digits[i + j] += total // 10
start = 0
while start < m + n - 1 and digits[start] == 0:
start += 1
return "".join(str(d) for d in digits[start:])
Python details:
int(num1[i])turns a single character such as'7'into the number 7. The string is never converted as a whole, which is the point of the lesson. Python's own integers could multiply two 1,000-digit numbers, but this exercise practises the digit method.%and//give the ones digit and the carry of a non-negative total.digits[start:]is a slice, a new list fromstartto the end. The generator expressionstr(d) for d in ...turns each digit into text, and"".joinglues the pieces with nothing in between.- Strings are immutable in Python, so the answer is built in a list of ints and joined once at the end, not by repeated string concatenation.
Complexity
Every pair of digits takes a constant number of steps, so the time is O(m · n). The skipping loop and the join add O(m + n). The list holds at most m + n digits, so the extra space is O(m + n).
Edge cases and common mistakes
- A zero factor.
"0"times"8317"leaves the list all zeros, and the skipping loop stops at the last position, giving"0". With a condition ofstart < m + ninstead, the loop would run off the end and the slice would be empty. - Leading zeros. Powers of ten such as
"100"times"100"give"10000". The list's first position can be 0 even for a non-zero answer, so it is skipped. - Wrong position. Using
i + jfor the product andi + j + 1for the carry puts the digits in the wrong columns. The ones digit goes to the right, ati + j + 1. - Forgetting the existing value. Setting
digits[i + j + 1] = product % 10instead of adding the earlier content throws away the results of previous pairs. - Maximum size.
"9"repeated 1,000 times, times itself, gives a 2,000-digit answer, which fits in them + npositions.
Testing
| num1 | num2 | result |
|---|---|---|
"25" | "16" | "400" |
"999" | "99" | "98901" |
"0" | "8317" | "0" |
"9" | "9" | "81" |
"100" | "100" | "10000" |
