TL;DR
Grade-school multiplication into a position array: digit i times digit j contributes to place i + j — O(m·n) time, O(m + n) space.
Approach 1 — “Cheat” with a native integer (why it’s disallowed)
The tempting one-liner is to parse both strings, multiply, and stringify:
def multiply(num1: str, num2: str) -> str:
return str(int(num1) * int(num2)) # not allowed by the problem
Python handles the 400-digit result correctly because its int is arbitrary precision. But the problem asks you to implement that big-integer multiply, and in a language with fixed-width integers this overflows. So the arithmetic is simulated by hand.
Approach 2 — Partial products with string addition
Long multiplication: multiply num1 by each single digit of num2, shift the result left by that digit’s position, and sum the partial products. The only primitives needed are “multiply a digit string by one digit” and “add two digit strings,” both done with carries.
def multiply(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
def add(a: str, b: str) -> str:
i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
while i >= 0 or j >= 0 or carry:
da = int(a[i]) if i >= 0 else 0
db = int(b[j]) if j >= 0 else 0
s = da + db + carry
out.append(str(s % 10))
carry = s // 10
i -= 1
j -= 1
return "".join(reversed(out))
result = "0"
# num2's rightmost digit has shift 0, next has shift 1, ...
for shift, dch in enumerate(reversed(num2)):
d = int(dch)
carry, partial = 0, []
for ch in reversed(num1):
p = int(ch) * d + carry
partial.append(str(p % 10))
carry = p // 10
if carry:
partial.append(str(carry))
partial_str = "".join(reversed(partial)) + "0" * shift
result = add(result, partial_str)
return result
Walkthrough with num1 = "123", num2 = "456":
- shift 0, digit
6: 123 * 6 = 738, no trailing zeros → partial "738"; result = "738".
- shift 1, digit
5: 123 * 5 = 615, append one 0 → "6150"; result = 738 + 6150 = "6888".
- shift 2, digit
4: 123 * 4 = 492, append two 0s → "49200"; result = 6888 + 49200 = "56088".
Complexity: O(m·n) work to form the partials, plus O(m + n) per string addition repeated n times → O(m·n) time, O(m + n) space.
Approach 3 — Position array (the clean one)
There is no need to build and re-add strings. Indexing digits from the right, the product of num1’s digit i and num2’s digit j contributes to decimal place i + j, spilling a carry into place i + j + 1. Accumulate every single-digit product into an integer array sized m + n, then resolve all carries in one pass.
def multiply(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
digits = [0] * (m + n)
for i in range(m - 1, -1, -1):
d1 = ord(num1[i]) - 48
for j in range(n - 1, -1, -1):
d2 = ord(num2[j]) - 48
# place i + j + 1 is the "units" slot for this pair
total = digits[i + j + 1] + d1 * d2
digits[i + j + 1] = total % 10
digits[i + j] += total // 10
# skip leading zeros, then join
start = 0
while start < len(digits) - 1 and digits[start] == 0:
start += 1
return "".join(str(x) for x in digits[start:])
Walkthrough with num1 = "123", num2 = "456" (m = n = 3, array length 6, indices 0..5):
i = 2 (3) × j = 2 (6) = 18 → slot 5 becomes 8, carry 1 into slot 4.i = 2 (3) × j = 1 (5) = 15, plus slot 4’s carry 1 = 16 → slot 4 = 6, carry 1 into slot 3.- Continuing every pair and letting carries ripple left, the array settles to
[0, 5, 6, 0, 8, 8].
- Strip the single leading
0 → "56088".
The intermediate total is computed on its own line before it is written back: the repo’s link checker flags an indexed value immediately followed by a call parenthesis, so indexing and any call are kept on separate lines.
Complexity: O(m·n) time — one addition per digit pair — and O(m + n) space for the array.
Common pitfalls
- Forgetting the
"0" short-circuit: without it you can emit "000" and then strip everything, or waste work; returning early is cleanest.
- Off-by-one on the carry slot — the units of
d1*d2 go to i + j + 1, the carry to i + j. Swapping them shifts the whole answer.
- Stripping all leading zeros so aggressively that a genuine
"0" result becomes ""; stop stripping while at least one digit remains.
- Reversing (or not reversing) the digit strings inconsistently between the multiply and add helpers.
Pattern takeaway
Simulating arithmetic on digit arrays is a recurring “math” move: index from the least-significant end, know exactly which output place each partial product lands in (i + j), accumulate first and propagate carries in a single sweep afterward. The same “sum into a positions array, then normalize carries” template covers big-integer add, multiply, and base conversions.