In this article
Before you start
Why interviewers ask this
Multiply Strings is a favourite of coding rounds because it looks trivial and then punishes every shortcut. The task is to reproduce what you learnt in school, but the rules take away the one tool that makes it easy: you may not turn the inputs into integers, so you must do the arithmetic yourself, digit by digit. That tests whether you can turn a hand procedure into index arithmetic, keep a carry correct across a loop, and handle the dull cases, such as a zero input, without being told.
The problem statement on LeetCode gives inputs of 1 to 200 digits (read 2026-10-24), so a quadratic method is fast enough. A weak answer builds a long list of partial products and adds them with another routine. A strong answer fills one array in place, explains why it has m plus n cells, and states the cost. The coding interviews hub places it beside the other string and array patterns, and the same single-pass habit appears in merge intervals and the monotonic stack.
Multiply Strings from first principles
- Multiply Strings
- Multiply Strings is a coding problem in which two non-negative integers are given as strings of decimal digits and their product must be returned as a string, so the arithmetic is done on characters rather than on a built-in number type.
- Long multiplication
- Long multiplication is the school method that multiplies one digit of a number by every digit of the other, shifts each row left by the digit's place value, and adds the rows, taking a total time proportional to the product of the two lengths.
- Carry
- A carry is the part of a digit-level result that does not fit in one decimal place, the tens part of a number from 0 to 99, which is added to the next place to the left.
In plain words
Think of multiplying on paper. The answer sits in a row of boxes, one per place value: ones, tens, hundreds. Take one digit from each number and multiply them. Write the units of the result in the matching box. The tens part goes in the box to its left. You keep one row of boxes and add each new result straight into it. The analogy breaks in one place.
On paper you see the page and pick the box by eye. Code must compute the box from two positions, and that is where the index arithmetic lives. Stated precisely, the product of an m-digit and an n-digit number fits in m plus n digits. The pair at positions i and j adds to cells i plus j and i plus j plus one.
Step 1: Allocate m plus n cells
The first step makes the place to put the answer. The input is the two strings, a with m digits and b with n digits; the output is a list of m plus n cells, a cell being one slot that will hold one decimal digit, all set to zero. The size is exact: a number with m digits is below 10 to the power m, one with n digits is below 10 to the power n, so the product is below 10 to the power m plus n and cannot need more digits.
A check on 2,000 random pairs found that the product always had either m plus n or m plus n minus one digits, never another count, which is why one spare cell at the left is enough and sometimes stays zero.1 Also decide now that a zero in either input means the answer is the string "0", which you can return at once.
Step 2: Multiply one pair of digits and add the cell
The second step does the arithmetic for one pair. The input is digit i of a and digit j of b, counted from the left starting at zero; the output is one number to be placed: the digit product (0 to 81) plus what the cell already holds, at most 99.1 Convert each character to its value by subtracting the character code of "0", then multiply.
Add whatever the target cell already holds, because earlier pairs may have left a partial sum there. Work from the right: loop i from the last digit down, and j from the last digit down, so that the ones digits are handled first and each carry travels toward cells that have not been finished yet. What you now know: the value to place is the digit product plus the current content of cell i plus j plus one.
Step 3: Write the digit and pass the carry left
The third step stores the result in two places, and it is where the common error lives. The input is the number from Step 2; the output is two changes. The units digit, the number modulo 10, replaces the content of cell i plus j plus one. The tens part, the number divided by 10 with the remainder dropped, is added to cell i plus j, the neighbour on the left.
Put the carry into the wrong cell, or forget it, and the answer is wrong from the first column that overflows. In the cross-check below, a version that dropped the carry failed 4,783 of 5,000 random multiplications, which makes it the most expensive single line of the function.1 The cell at i plus j can temporarily hold more than 9, which is fine, because the loop reaches it later as the cell i plus j plus one of a pair further left and splits it then.
Step 4: Trim leading zeros
The fourth step turns the cells into the answer string. The input is the filled list; the output is the digits joined into text, with leading zeros removed and the string "0" returned if nothing remains. The leading cell is zero whenever the product has m plus n minus one digits, as in 12 times 3, whose cells read 0, 3 and 6 and whose answer is 36.1
Without the trim, 908 of the 5,000 random tests returned the right digits with a stray zero in front, a wrong string.1 The trim's fallback to "0" also covers a zero input, so the guard of Step 1 is an early exit; with neither the guard nor the trim, 0 times 123 returns "0000".1
Step-by-step description
- Make m plus n cells, all zero.
- Multiply digit i by digit j and add the cell.
- Keep the units digit and pass the tens left.
- Drop leading zeros, return 0 if nothing is left.
- The result array has m plus n cells, all zero at the start.
- Digit i times digit j goes to cell i plus j plus one, with the carry added to cell i plus j.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
The input is 123 times 456 (Example 2 of the LeetCode problem), so m and n are both 3 and the array has 6 cells, all zero. Take the digit 3 of 123 first, against 6, 5 and 4 in turn: the cells become 0 0 1 3 6 8, which is 3 times 456, or 1,368. The digit 2 adds 2 times 456 shifted one cell left, and the cells read 0 1 0 4 8 8, which is 10,488. The digit 1 adds 456 shifted two cells left, and the cells read 0 5 6 0 8 8, which is 56,088. Trimming the leading zero returns "56088", the same as the integer product.1
Text description of the diagram
- After the digit 3 the cells read 0 0 1 3 6 8.
- After the digit 2 the cells read 0 1 0 4 8 8.
- After the digit 1 the cells read 0 5 6 0 8 8, and trimming the leading zero gives 56088.
| Fact | Value |
|---|---|
| Example input | 123 times 456 |
| Cells after each digit of 123, right to left | 0 0 1 3 6 8, then 0 1 0 4 8 8, then 0 5 6 0 8 8 |
| Result after trimming | 56088 |
| Random inputs checked against Python integers | 5,000 (1 to 12 digits each, seed 0) |
| Inputs on which the cell method matched | 5,000 |
| Inputs on which dropping the carry was wrong | 4,783 |
| Inputs on which skipping the trim was wrong (zero guard kept) | 908 |
Here is the Python version that was run to produce those numbers.
def multiply(a, b):
if a == "0" or b == "0":
return "0"
m, n = len(a), len(b)
cells = [0] * (m + n)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
p = (ord(a[i]) - 48) * (ord(b[j]) - 48) + cells[i + j + 1]
cells[i + j + 1] = p % 10 # units digit stays here
cells[i + j] += p // 10 # tens part moves one cell left
return "".join(map(str, cells)).lstrip("0") or "0"The function reads the digits as character codes, since the code of "0" is 48, and never builds an integer from the inputs. The inner statement runs once per digit pair, so a 3 by 3 multiplication does 9 digit products and a 200 by 200 one does 40,000; as a final check, two strings of 200 nines produced a 400-digit product equal to Python's.1
Trade-offs and edge cases
Time and space. Long multiplication takes time proportional to m times n, written O(m*n), which for equal lengths n is the O(n²) that Wikipedia calls the oldest and simplest method; the cell array adds O(m+n) space. Faster methods exist. Karatsuba is a divide-and-conquer multiplication method that splits each number in half. Karatsuba's algorithm, found in 1960, replaces four half-size multiplications with three and runs in about n to the power 1.58, but its extra additions make it slower for small numbers (Wikipedia, Karatsuba algorithm, edited 8 October 2026). For the usual interview sizes, a few hundred digits at most, the simple method is the expected answer; mention Karatsuba as a one-sentence follow-up, not as code.
Why not convert to integers? In Python, integers have unlimited precision, so int(a) * int(b) works, and it is the right tool outside an interview. The rules of the problem forbid it, though, and Python has its own limit: since version 3.11 the default maximum for converting between a decimal string and an integer is 4,300 digits, raised as a ValueError, because no algorithm converts base-10 text to a binary integer in linear time (Python documentation, read 2026-10-24; sys module, read 2026-10-24). Other languages differ: fixed-width integers overflow, and JavaScript numbers lose precision for very large values.
Edge cases. A zero input, a single digit, inputs of different lengths and a product that is one digit shorter than m plus n are the four cases to test aloud. For another string problem solved in one pass, see longest substring without repeating characters, which tracks seen characters with a hash set. The interview loop overview shows where such a round sits.
How to answer it in an interview
Multiply two non-negative numbers given as strings, without converting them to integers.
I do long multiplication into an array of m plus n cells, because the product cannot have more digits than that. I loop over both strings from the right. For digits i and j, I add their product to the cell at i plus j plus one, keep the units digit there, and add the tens part to the cell at i plus j. At the end I trim leading zeros and return zero if nothing is left. I would handle a zero input first. The time is proportional to m times n, and the extra space is m plus n.
The spoken structure is: size the array, place the digit and the carry, trim, then state the cost.
Common mistakes
Dropping the carry. (wrong) "I store the units digit and move on." (right) "I add the tens part to the cell on the left." Without it, 4,783 of 5,000 random products were wrong.1
Forgetting to trim. (wrong) "The array is the answer." (right) "I strip leading zeros, and return 0 if the string is empty." Keeping leading zeros in the output makes the string wrong, and twelve times three gives "036" otherwise.1
Converting with int(). (wrong) "I convert both strings, multiply, and convert back." (right) "The problem asks for digit arithmetic, and Python stops converting past the default digit limit described above (more in Python interview questions)."
Looping left to right. (wrong) Starting at the first digit so each carry has to travel backward into cells already used. (right) Start at the last digit, as school multiplication does, so the carry always moves toward cells still open.
Text description of the diagram
- Dropping the carry failed on 4,783 of 5,000 random tests.
- Skipping the trim, with the zero guard kept, failed on 908 of 5,000 tests.
- The default limit for converting between decimal strings and integers is 4,300 digits.
Follow-up questions
How do you add two numbers given as strings?
Walk both strings from the right with one carry that starts at zero, add the two digits and the carry, keep the units digit and carry the tens part, and continue until both strings and the carry are used up. The cost is linear in the longer length. This is the building block that the school method adds rows with, and it is the same carry rule as Step 3.
Can you multiply faster than O(m*n)?
Yes, for very large numbers. Karatsuba's algorithm splits each number in half and uses three half-size products instead of four, which gives about n to the power 1.58 (Wikipedia, Karatsuba algorithm, edited 8 October 2026). It is not worth writing in a round unless the interviewer asks.
Why does the product need m plus n cells?
An m-digit number is below 10 to the power m and an n-digit number is below 10 to the power n, so the product is below 10 to the power m plus n and has at most that many digits. In 2,000 random pairs it had m plus n or one fewer.1
What if the digits arrive in a stream?
If the digits of one number arrive from the left, keep a running product and, for each new digit d, update it as product = product x 10 + d x b, where b is the other number as a string. The multiply-by-10 is just appending a zero cell. Add d x b into the rightmost n + 1 cells, then keep passing the carry left until it is zero; every cell left of where the carry stops is unchanged. The total work stays proportional to m times n, while a full-length string add at every step would grow with m squared. The Horner update was checked against Python's integer product on a 30-digit stream.1
What if the numbers are in base 2?
Replace 10 in the modulo and division with the base; the structure is unchanged. Base 2 digits are bits, so the same carry rule works on bit strings; Hamming distance and little-endian byte order are neighbouring bit-level topics.
What changes for negative numbers or decimals?
Handle the sign separately: multiply the absolute values, and put a minus sign in front only if exactly one input was negative and the product is not "0", so "-0" never appears. For decimals, drop the point, multiply as integers, and put the point back so that the digits after it number the sum of the two inputs' digits after the point.
- Allocate m plus n cells; the product never needs more.
- Digit i times digit j goes to cell i plus j plus one, with the carry added to cell i plus j.
- Loop from the right, and trim leading zeros at the end.
- The cost is O(m*n) time and O(m+n) space.
- Do not convert the inputs to integers; the problem forbids it.
Sources
- Built-in Types: Integer string conversion length limitation (Python 3 documentation) — Python Software Foundation (date = read date), 24 Oct 2026
- sys: get_int_max_str_digits and set_int_max_str_digits (Python 3 documentation) — Python Software Foundation (date = read date), 24 Oct 2026
- Multiply Strings (LeetCode problem 43) — LeetCode (date = read date), 24 Oct 2026
- Multiplication algorithm — Wikipedia (date = read date), 24 Oct 2026
- Karatsuba algorithm — Wikipedia (last edited 8 October 2026), 8 Oct 2026
