Multiply Strings
Asked at Pinterest
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.
Asked At
| 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.
Visual walkthrough for "123" * "45":
res = [0,0,0,0,0]
i=2 (3): 3*5=15 -> res[4]=5, res[3]+=1; 3*4=12 -> res[3]=13 -> res[3]=3, res[2]+=1
i=1 (2): 2*5=10 -> res[3]=13 -> 3, res[2]+=1; 2*4=8 -> res[2]=10 -> 0, res[1]+=1
i=0 (1): 1*5=5 -> res[2]=5; 1*4=4 -> res[1]=5
res = [0,5,5,3,5] -> "5535"
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.