#43 Multiply Strings
the problem
In plain words
num1 and num2 are non-negative integers written as strings of digits (up to 200 digits each). Return their product as a string. You may not use BigInteger or convert the whole inputs into numbers.
in num1 = "2", num2 = "3"
out "6"
in num1 = "123", num2 = "456"
out "56088"
- 1 ≤ num1.length, num2.length ≤ 200
- Digits only
- No leading zeros, except the number 0 itself
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSimulation
In school multiplication, digit i of num1 times digit j of num2 always lands in column i + j + 1 of an (m + n)-digit answer. Add every product into its column, push carries left, and you never need to add whole strings.
solutions
From brute force to optimal
Let the library do it — useful to check your answers offline, but the problem forbids it.
- new BigInteger(num1).multiply(new BigInteger(num2)).toString().
200-digit inputs are below BigInteger's Karatsuba threshold (80 ints ≈ 770 digits), so it multiplies schoolbook-style too.
The product's digits.
class Solution { public String multiply(String num1, String num2) { // Correct, but the problem forbids it. Good for checking your own answers offline. return new BigInteger(num1).multiply(new BigInteger(num2)).toString(); }}Multiply num1 by one digit of num2 at a time (with shifted zeros) and add each row into a running total string.
- For each digit of num2 from the right: build num1 × digit, followed by
shiftzeros. - Add that row to the total with a carry loop.
n rows; each costs O(m) to build and O(m + n) to add.
One row and the running total.
class Solution { public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) return "0"; String total = "0"; for (int j = num2.length() - 1, shift = 0; j >= 0; j--, shift++) { StringBuilder row = new StringBuilder("0".repeat(shift)); // built backwards, so the shift zeros go first int carry = 0, d2 = num2.charAt(j) - '0'; for (int i = num1.length() - 1; i >= 0; i--) { int p = (num1.charAt(i) - '0') * d2 + carry; row.append(p % 10); carry = p / 10; } if (carry > 0) row.append(carry); total = add(total, row.reverse().toString()); // one row of school multiplication } return total; } private static String add(String a, String b) { StringBuilder sb = new StringBuilder(); int i = a.length() - 1, j = b.length() - 1, carry = 0; while (i >= 0 || j >= 0 || carry > 0) { int sum = carry + (i >= 0 ? a.charAt(i--) - '0' : 0) + (j >= 0 ? b.charAt(j--) - '0' : 0); sb.append(sum % 10); carry = sum / 10; } return sb.reverse().toString(); }}Every digit product has a fixed column: add it there and carry left as you go.
- pos = new int[m + n].
- For i from m−1 down, j from n−1 down: sum = d1·d2 + pos[i+j+1]; pos[i+j+1] = sum % 10; pos[i+j] += sum / 10.
- Skip leading zeros (keep at least one digit) and join.
One multiply-add per pair of digits: 40,000 for two 200-digit numbers.
The column array — the product has at most m + n digits.
class Solution { public String multiply(String num1, String num2) { int m = num1.length(), n = num2.length(); int[] pos = new int[m + n]; // the product has at most m + n digits for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); int sum = mul + pos[i + j + 1]; // digit i times digit j lands at i + j + 1 pos[i + j + 1] = sum % 10; pos[i + j] += sum / 10; // the carry moves one place left } } int k = 0; while (k < pos.length - 1 && pos[k] == 0) k++; // skip leading zeros, keep at least one digit StringBuilder sb = new StringBuilder(); for (; k < pos.length; k++) sb.append(pos[k]); return sb.toString(); }}in the room
How to say it in the interview
talk track
- Write 123 × 456 on the board and point at where 3 × 6 and 2 × 5 land: columns i + j + 1.
- Explain why m + n digits are enough: the product is below 10ᵐ × 10ⁿ.
- Handle "0" by skipping leading zeros but keeping the last digit.
traps
- Returning "0000" for "0" × "1234".
- Converting to
long— 200 digits is far beyond 19.
what they ask next
Follow-ups
Faster for really huge numbers?
Karatsuba multiplies in O(n^1.585). Java's BigInteger switches to Karatsuba above 80 ints and to Toom-Cook 3 above 240 ints.
before you submit
Edge cases to test
- Either input is "0" → "0" (not "000")
- A carry creates a new leading digit: "9" × "9" = "81"
- Maximum size: 200 × 200 digits → up to 400 digits
practise next
Similar problems
- #66Plus OneEasyin Math & Numbers
- #2Add Two NumbersMediumin Linked Lists