43. Multiply Strings
Asked at Pinterest
Difficulty
Medium
Time
O(m * n)
Space
O(m + n)
Pattern
Math
Companies
1
Problem
You are given two non-negative integers as decimal strings, num1 and num2. Return their product, also as a string.
The catch: you may not use a big-integer library, and you may not convert the whole string to an integer first. The inputs can be up to 200 digits long, so no normal number type can hold them. You must simulate multiplication digit by digit, the way you do it on paper.
Each input has no leading zeros, except the single digit "0" itself. The result must also have no leading zeros — the product of "0" and anything is just "0".
Multiply two digit strings
Constraints
- ●
1 <= num1.length, num2.length <= 200 - ●
num1 and num2 consist of digits only - ●
num1 and num2 have no leading zeros, except the value 0 itself
Examples
num1 = "2", num2 = "3""6"num1 = "123", num2 = "456""56088"Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Medium | View all Pinterest questions → |
How to Think About It
Converting to int fails immediately — the inputs can be up to 200 digits long, far past any 64-bit type. You have to simulate multiplication digit by digit.
Key insight: when you multiply digit num1[i] by digit num2[j], the product lands in positions i + j and i + j + 1 of the result. A result of an m-digit and n-digit number has at most m + n digits, so allocate an array of that size.
Walk both strings from right to left. For each pair, add d1 * d2 to res[i + j + 1], then push the carry into res[i + j]. Doing the carry immediately keeps every cell in the range 0-9 except the one you just wrote to.
Edge cases: either input is "0" (answer is "0", not "00"), leading zeros in the result array must be stripped, and single-digit inputs.
Optimal Approach
Step 1: If either number is "0", return "0".
Step 2: Create res of length m + n filled with zeros.
Step 3: For i from m-1 down to 0 and j from n-1 down to 0:
p = digit(num1[i]) * digit(num2[j]) + res[i + j + 1]
res[i + j + 1] = p % 10
res[i + j] += p // 10
Step 4: Skip leading zeros in res and join the remaining digits.
Every digit pair is visited once, so the work is proportional to m * n.
Time: O(m * n). Space: O(m + n).
Grade-school long multiplication
What Trips People Up in Real Interviews
Reaching for int(num1) * int(num2). It works in Python but defeats the purpose — say out loud that you are simulating long multiplication because the inputs overflow fixed-width integers.
Getting the positions wrong. The product of num1[i] and num2[j] belongs at i + j + 1 with carry into i + j. Derive it from a tiny example before coding rather than guessing.
Returning "0000" for inputs like "0" and "99". Either short-circuit on zero or strip leading zeros carefully while keeping at least one digit.
Forgetting that res[i + j] can temporarily exceed 9. That is fine — it gets normalized when a later (more significant) iteration writes to that cell as its i + j + 1 position.
Solution Code
O(m * n) timedef multiply(num1, num2):
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
res = [0] * (m + n)
for i in range(m - 1, -1, -1):
d1 = ord(num1[i]) - ord('0')
for j in range(n - 1, -1, -1):
d2 = ord(num2[j]) - ord('0')
p = d1 * d2 + res[i + j + 1]
res[i + j + 1] = p % 10
res[i + j] += p // 10
k = 0
while k < len(res) - 1 and res[k] == 0:
k += 1
return ''.join(map(str, res[k:]))Frequently Asked Questions
What is the Multiply Strings problem?
Multiply Strings gives you two non-negative integers written as decimal strings and asks for their product, also as a string. You are not allowed to convert the inputs to built-in big integers, so the interviewer is really asking whether you can implement grade-school long multiplication cleanly with the right index arithmetic.
How do you solve Multiply Strings?
The optimal approach runs in O(m * n) time and O(m + n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Multiply Strings?
Multiply Strings is asked at Pinterest. It is a medium difficulty problem.
What are common mistakes on Multiply Strings?
- Reaching for `int(num1) * int(num2)`. It works in Python but defeats the purpose — say out loud that you are simulating long multiplication because the inputs overflow fixed-width integers.
- Getting the positions wrong. The product of `num1[i]` and `num2[j]` belongs at `i + j + 1` with carry into `i + j`. Derive it from a tiny example before coding rather than guessing.
- Returning `"0000"` for inputs like `"0"` and `"99"`. Either short-circuit on zero or strip leading zeros carefully while keeping at least one digit.
- Forgetting that `res[i + j]` can temporarily exceed 9. That is fine — it gets normalized when a later (more significant) iteration writes to that cell as its `i + j + 1` position.