Multiply two non-negative numbers given as strings, and return the product as a string. You may not convert them to integers or use a big-integer library.
Restating the Problem: You are given two numbers represented as strings. You must multiply them and return the result as a string. The catch is that you cannot just convert them to int and multiply them directly, because in the real world (or languages without arbitrary precision), these numbers would overflow standard data types.
Constraints to note: Both strings consist only of digits and can be up to 200 characters long.
Edge cases: Multiplying by "0" should yield exactly "0", avoiding "000".
The "brute force" here isn't an algorithm, but rather the cheating approach: return str(int(num1) * int(num2)). This works natively in Python because Python automatically handles arbitrarily large integers. However, this violates the spirit of the question. The intended naive approach is simulating repeated addition (adding num1 to itself num2 times), but that would take O(10^{\text{len}(num2)}) operations, which is astronomically slow. We must simulate long multiplication.
Long multiplication, as taught in school — but instead of writing down partial products and adding them up, accumulate everything into one array.
The index formula is the whole problem:
Multiplying digit i of num1 by digit j of num2 contributes to positions i + j and i + j + 1 of the result.
Both indices count from the left, and the result array has length m + n.
Why i + j and i + j + 1. Digit i from the left of an m-digit number has place value 10^{m-1-i}. Multiplying two such digits gives place value 10^{(m-1-i) + (n-1-j)} = 10^{(m+n-2) - (i+j)} — which is position i + j + 1 in an array of length m + n, counting from the left. The carry goes one position further left, at i + j.
Check it on the smallest case rather than trusting the algebra."12" × "34": the last digits are i = 1 and j = 1, giving i + j + 1 = 3 — the final position of a 4-length array ✓.
Two numbers of m and n digits multiply to at most m + n digits, and at least m + n − 1. So allocate m + n and strip at most one leading zero at the end.
99 × 99 = 9801 — four digits from two twos. 10 × 10 = 100 — three digits, so one leading zero to strip.
class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": # (1) return "0" # avoids "000" m, n = len(num1), len(num2) result = [0] * (m + n) # (2) for i in range(m - 1, -1, -1): # (3) right to left for j in range(n - 1, -1, -1): # (4) product = int(num1[i]) * int(num2[j]) # (5) total = product + result[i + j + 1] # (6) add what is already there result[i + j + 1] = total % 10 # (7) keep the units digit result[i + j] += total # (8) 10 # carry left # strip a single leading zero if present start = 1 if result[0] == 0 else 0 # (9) return ''.join(map(str, result[start:]))
ts
function multiply(num1: string, num2: string): string { if (num1 === "0" || num2 === "0") return "0"; // (1) const m = num1.length, n = num2.length; const result = new Array(m + n).fill(0); // (2) for (let i = m - 1; i >= 0; i--) { // (3) for (let j = n - 1; j >= 0; j--) { // (4) const product = Number(num1[i]) * Number(num2[j]); // (5) const total = product + result[i + j + 1]; // (6) result[i + j + 1] = total % 10; // (7) result[i + j] += Math.floor(total / 10); // (8) } } const start = result[0] === 0 ? 1 : 0; // (9) return result.slice(start).join('');}
This is long multiplication from school, done digit by digit, with every partial result added into one row of answer digits.
(1) Anything times zero is zero. Return "0" directly. Otherwise the answer would come out as a row of zeros like "000".
(2) The answer has at most m + n digits. For example, 99 \times 99 = 9801: two digits times two digits gives four. Each slot will hold one digit of the answer.
(3) Take each digit of num1, from the right, and
(4) multiply it by each digit of num2, from the right.
(5) Multiply the two single digits.int(num1[i]) turns the character '7' into the number 7.
(6) Add whatever is already in the slot this product belongs in. The digit at position i of num1 times the digit at position j of num2 lands in slot i + j + 1. Counting from the left, that is exactly the place value the two digits create together.
(7) Keep only the ones digit in that slot.
(8) Carry the tens part one slot to the left. That slot may now hold 10 or more for a moment. That is fine, because it will be tidied when a later step adds into it and keeps only its ones digit.
(9) The first slot may be an unused 0, as when 12 \times 12 = 144 uses only three of four slots. Skip it, then join the digits into a string.
O(mn) time — every pair of digits is multiplied once. O(m + n) space.
Time Complexity:O(mn). We have two nested loops, one iterating m times and the other n times. Each inner step does O(1) arithmetic operations.
Space Complexity:O(m + n). We allocate a result array of size m + n to store the intermediate digits.
Faster algorithms exist, and naming one is a good finish:
Karatsuba — O(n^{1.585}), by reducing four half-size multiplications to three. It is the standard example of divide-and-conquer beating the obvious bound, and 4.12 derives it.
Fast Fourier Transform based methods — O(n \log n), used by real big-integer libraries for very large numbers.
Python switches to Karatsuba above a few thousand digits. At 200 digits the schoolbook method wins on constants, which is why this is the right algorithm here.
Big-integer libraries — every one of them is this loop, in a base like 2^{32} rather than 10, because a larger base means fewer digits and fewer carries.
"Derive the index formula." Place values multiply, so the exponents add — and check it on "12" × "34".
"How long can the result be?"m + n at most, m + n − 1 at least, hence a single leading zero to strip.
"Why += and not =?" Several pairs land on the same position, and carries accumulate.
"Why does the carry not need normalising immediately?" The right-to-left order means that position is visited later, and it normalises then.
"Can you do better than O(mn)?" Karatsuba, then FFT. Say why they do not help at 200 digits.
One thing to volunteer: verify the index formula on a two-by-two example out loud before writing the loops. It is the only part of this problem that can be wrong, and checking it costs ten seconds.
Next:4.28.8 Detect Squares — geometry with a counting map, and the last problem in this group.