Multiply Strings
Multiply Strings is a medium arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (position array), runs in O(n · m) time and O(n + m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (schoolbook with string additions) up.
Problem
Given two non-negative integers num1 and num2 written as decimal strings, return their product, also as a decimal string.
You may not use a built-in big-number library or convert either input to an integer directly; compute the product digit by digit.
Examples
Example 1
- Input
num1 = "12", num2 = "34"- Output
"408"- Why
- 12 × 34 = 408.
Example 2
- Input
num1 = "999", num2 = "99"- Output
"98901"- Why
- Carries ripple through every column of the product.
Example 3
- Input
num1 = "5021", num2 = "0"- Output
"0"- Why
- Anything times zero is "0", with no extra leading zeros.
Constraints
1 <= num1.length, num2.length <= 200- Both strings contain only digits and have no leading zeros, except the number
0itself. - Do not convert the inputs to built-in big-integer types or parse them as whole numbers.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (schoolbook with string additions) | O(m · (n + m)) | O(n + m) |
| Optimal (position array) | O(n · m) | O(n + m) |
1Brute force (schoolbook with string additions)
O(m · (n + m))Each of the m digits of num2 builds a partial product and adds it to a total of length up to n + m.O(n + m)The partial product and the running total.Multiply num1 by each digit of num2 separately, producing a partial product string, pad it with zeros for its place value, and add it into a running total using digit-by-digit string addition.
- If either input is "0", return "0".
- For each digit d of num2 from the right (place k = 0, 1, …): partial = num1 × d (single-digit multiply with carry) followed by k zeros.
- total = addStrings(total, partial).
- Return total.
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
String total = "0";
for (int k = 0; k < num2.length(); k++) {
int d = num2.charAt(num2.length() - 1 - k) - '0';
StringBuilder partial = new StringBuilder();
int carry = 0;
for (int i = num1.length() - 1; i >= 0; i--) {
int p = (num1.charAt(i) - '0') * d + carry;
partial.append(p % 10);
carry = p / 10;
}
if (carry > 0) partial.append(carry);
partial.reverse();
for (int z = 0; z < k; z++) partial.append('0');
total = add(total, partial.toString());
}
return total;
}
private 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 s = carry;
if (i >= 0) s += a.charAt(i--) - '0';
if (j >= 0) s += b.charAt(j--) - '0';
sb.append(s % 10);
carry = s / 10;
}
return sb.reverse().toString();
}
}class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
total = "0"
for k in range(len(num2)):
d = ord(num2[len(num2) - 1 - k]) - 48
partial = []
carry = 0
for i in range(len(num1) - 1, -1, -1):
p = (ord(num1[i]) - 48) * d + carry
partial.append(str(p % 10))
carry = p // 10
if carry > 0:
partial.append(str(carry))
total = self.add(total, "".join(reversed(partial)) + "0" * k)
return total
def add(self, a: str, b: str) -> str:
out = []
i, j, carry = len(a) - 1, len(b) - 1, 0
while i >= 0 or j >= 0 or carry > 0:
s = carry
if i >= 0:
s += ord(a[i]) - 48
i -= 1
if j >= 0:
s += ord(b[j]) - 48
j -= 1
out.append(str(s % 10))
carry = s // 10
return "".join(reversed(out))class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
string total = "0";
int m = num2.size();
for (int k = 0; k < m; k++) {
int d = num2[m - 1 - k] - '0';
string partial;
int carry = 0;
for (int i = (int)num1.size() - 1; i >= 0; i--) {
int p = (num1[i] - '0') * d + carry;
partial.push_back('0' + p % 10);
carry = p / 10;
}
if (carry > 0) partial.push_back('0' + carry);
reverse(partial.begin(), partial.end());
partial.append(k, '0');
total = add(total, partial);
}
return total;
}
private:
string add(const string& a, const string& b) {
string out;
int i = a.size() - 1, j = b.size() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int s = carry;
if (i >= 0) s += a[i--] - '0';
if (j >= 0) s += b[j--] - '0';
out.push_back('0' + s % 10);
carry = s / 10;
}
reverse(out.begin(), out.end());
return out;
}
};function multiply(num1, num2) {
if (num1 === "0" || num2 === "0") return "0";
let total = "0";
const m = num2.length;
for (let k = 0; k < m; k++) {
const d = num2.charCodeAt(m - 1 - k) - 48;
const partial = [];
let carry = 0;
for (let i = num1.length - 1; i >= 0; i--) {
const p = (num1.charCodeAt(i) - 48) * d + carry;
partial.push(p % 10);
carry = Math.floor(p / 10);
}
if (carry > 0) partial.push(carry);
total = add(total, partial.reverse().join("") + "0".repeat(k));
}
return total;
}
function add(a, b) {
const out = [];
let i = a.length - 1, j = b.length - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
let s = carry;
if (i >= 0) s += a.charCodeAt(i--) - 48;
if (j >= 0) s += b.charCodeAt(j--) - 48;
out.push(s % 10);
carry = Math.floor(s / 10);
}
return out.reverse().join("");
}2Optimal (position array)
O(n · m)Every pair of digits is multiplied exactly once.O(n + m)The result array of n + m digits.The product of an n-digit and an m-digit number has at most n + m digits. Digit num1[i] times digit num2[j] contributes to positions i + j (tens) and i + j + 1 (units) of the result. Add every such product into an int array, carrying as you go from the right, then read the array skipping leading zeros.
- If either input is "0", return "0".
- pos = int[n + m].
- For i from n - 1 down to 0, for j from m - 1 down to 0: sum = d1 × d2 + pos[i + j + 1]; pos[i + j + 1] = sum % 10; pos[i + j] += sum / 10.
- Build the string from pos, skipping leading zeros.
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
int n = num1.length(), m = num2.length();
int[] pos = new int[n + m];
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int sum = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + pos[i + j + 1];
pos[i + j + 1] = sum % 10;
pos[i + j] += sum / 10;
}
}
StringBuilder sb = new StringBuilder();
for (int d : pos) {
if (sb.length() == 0 && d == 0) continue;
sb.append(d);
}
return sb.toString();
}
}class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
n, m = len(num1), len(num2)
pos = [0] * (n + m)
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
s = (ord(num1[i]) - 48) * (ord(num2[j]) - 48) + pos[i + j + 1]
pos[i + j + 1] = s % 10
pos[i + j] += s // 10
out = []
for d in pos:
if not out and d == 0:
continue
out.append(str(d))
return "".join(out)class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int n = num1.size(), m = num2.size();
vector<int> pos(n + m, 0);
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int sum = (num1[i] - '0') * (num2[j] - '0') + pos[i + j + 1];
pos[i + j + 1] = sum % 10;
pos[i + j] += sum / 10;
}
}
string out;
for (int d : pos) {
if (out.empty() && d == 0) continue;
out.push_back('0' + d);
}
return out;
}
};function multiply(num1, num2) {
if (num1 === "0" || num2 === "0") return "0";
const n = num1.length, m = num2.length;
const pos = new Array(n + m).fill(0);
for (let i = n - 1; i >= 0; i--) {
for (let j = m - 1; j >= 0; j--) {
const sum = (num1.charCodeAt(i) - 48) * (num2.charCodeAt(j) - 48) + pos[i + j + 1];
pos[i + j + 1] = sum % 10;
pos[i + j] += Math.floor(sum / 10);
}
}
let out = "";
for (const d of pos) {
if (out.length === 0 && d === 0) continue;
out += d;
}
return out;
}Edge cases to test
- One factor is "0": the answer is exactly "0"
- Single-digit factors, like "9" × "9"
- Long inputs (200 digits) whose product does not fit any primitive type
- Products where every column carries, like 999 × 999
Hints
Hint 1
Do it the way you learned on paper: multiply by one digit at a time, shift, and add.
Hint 2
Digit i of num1 times digit j of num2 always lands in positions i + j and i + j + 1 of the result (indexing from the left).
Hint 3
Accumulate all products into an int array of length m + n, push carries, then skip leading zeros.
FAQ
What is the best time complexity for Multiply Strings?
Optimal (position array) runs in O(n · m) time and O(n + m) extra space. Every pair of digits is multiplied exactly once.
Which pattern does Multiply Strings use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.
Is there a brute force solution for Multiply Strings?
Yes. Brute force (schoolbook with string additions) takes O(m · (n + m)) time and O(n + m) space. Multiply num1 by each digit of num2 separately, producing a partial product string, pad it with zeros for its place value, and add it into a running total using digit-by-digit string addition.
Which edge cases should I test for Multiply Strings?
One factor is "0": the answer is exactly "0"; Single-digit factors, like "9" × "9"; Long inputs (200 digits) whose product does not fit any primitive type; Products where every column carries, like 999 × 999.