Multiply Strings
How to Multiply Strings Representing Large Numbers.
Multiplying two numbers is a straightforward operation, but what if the numbers are represented as strings? And what if their lengths are large enough to cause overflow when using conventional methods?
In this article, we’ll explore an efficient approach to solve the problem of multiplying strings representing non-negative integers without relying on built-in conversion functions.
Problem Description
You are given two non-negative integers as strings, num1 and num2. Your task is to compute their product and return the result as a string.
- Constraints:
- You cannot convert the strings directly into integers using built-in functions.
- Neither
num1nornum2will contain leading zeros, except if the value itself is0.
Example 1
Input: num1 = "3", num2 = "4"
Output: "12"
Explanation:
- Query = 2: The interval [2,3] is the smallest one containing 2, it’s length is 2.
- Query = 3: The interval [2,3] is the smallest one containing 3, it’s length is 2.
- Query = 1: The interval [1,3] is the smallest one containing 1, it’s length is 3.
- Query = 7: The interval [3,7] is the smallest one containing 7, it’s length is 5.
- Query = 6: The interval [6,6] is the smallest one containing 6, it’s length is 1.
- Query = 8: There is no interval containing 8.
Example 2
Input: num1 = "111", num2 = "222"
Output: "24642"
Constraints:
- 1 <= num1.length, num2.length <= 200
- num 1 and num 2 consist of digits only.
Steps to Solve
Reverse the Strings:
Start with the least significant digit (rightmost) to perform multiplication, just like in manual multiplication.Create an Array for Intermediate Results:
Use an array of size len(num1)+len(num2) to store the results. This size ensures that the largest possible product fits.Multiply Digit by Digit:
Multiply each digit ofnum1with each digit ofnum2and store the result in the appropriate position in the result array.Handle Carries:
Adjust the result array for carries after all multiplications are done.Construct the Result String:
Skip leading zeros in the result array and combine digits into the final output string.
Challenges in Multiplying Strings
Handling Large Numbers:
Since the strings can be up to 200 digits long, directly converting them to integers is not feasible due to potential overflow or performance issues.Simulating Manual Multiplication:
Multiplication needs to be performed at the digit level, just like how we multiply numbers by hand on paper.Efficient Result Construction:
Managing intermediate results and carrying over values without excessive computational overhead can be tricky.
There are mainly Four approach to solve this problem –
- Brute Force
- Sweep Line Algorithm
- Min Heap
- Min Segment Tree (Lazy Propagation)
1. Multiplication & Addition
- Time complexity: O(min(m,n)∗(m+n))
- Space complexity: O(m+n)
Python
C++
Java
JavaScript
Python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
if len(num1) < len(num2):
return self.multiply(num2, num1)
res, zero = "", 0
for i in range(len(num2) - 1, -1, -1):
cur = self.mul(num1, num2[i], zero)
res = self.add(res, cur)
zero += 1
return res
def mul(self, s: str, d: str, zero: int) -> str:
i, carry = len(s) - 1, 0
d = int(d)
cur = []
while i >= 0 or carry:
n = int(s[i]) if i >= 0 else 0
prod = n * d + carry
cur.append(str(prod % 10))
carry = prod // 10
i -= 1
return ''.join(cur[::-1]) + '0' * zero
def add(self, num1: str, num2: str) -> str:
i, j, carry = len(num1) - 1, len(num2) - 1, 0
res = []
while i >= 0 or j >= 0 or carry:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
total = n1 + n2 + carry
res.append(str(total % 10))
carry = total // 10
i -= 1
j -= 1
return ''.join(res[::-1])C++
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
if (num1.size() < num2.size()) {
return multiply(num2, num1);
}
string res = "";
int zero = 0;
for (int i = num2.size() - 1; i >= 0; --i) {
string cur = mul(num1, num2[i], zero);
res = add(res, cur);
zero++;
}
return res;
}
string mul(string s, char d, int zero) {
int i = s.size() - 1, carry = 0;
int digit = d - '0';
string cur;
while (i >= 0 || carry) {
int n = (i >= 0) ? s[i] - '0' : 0;
int prod = n * digit + carry;
cur.push_back((prod % 10) + '0');
carry = prod / 10;
i--;
}
reverse(cur.begin(), cur.end());
return cur + string(zero, '0');
}
string add(string num1, string num2) {
int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
string res;
while (i >= 0 || j >= 0 || carry) {
int n1 = (i >= 0) ? num1[i] - '0' : 0;
int n2 = (j >= 0) ? num2[j] - '0' : 0;
int total = n1 + n2 + carry;
res.push_back((total % 10) + '0');
carry = total / 10;
i--;
j--;
}
reverse(res.begin(), res.end());
return res;
}
};Java
public class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
if (num1.length() < num2.length()) {
return multiply(num2, num1);
}
String res = "";
int zero = 0;
for (int i = num2.length() - 1; i >= 0; i--) {
String cur = mul(num1, num2.charAt(i), zero);
res = add(res, cur);
zero++;
}
return res;
}
private String mul(String s, char d, int zero) {
int i = s.length() - 1, carry = 0;
int digit = d - '0';
StringBuilder cur = new StringBuilder();
while (i >= 0 || carry > 0) {
int n = (i >= 0) ? s.charAt(i) - '0' : 0;
int prod = n * digit + carry;
cur.append(prod % 10);
carry = prod / 10;
i--;
}
return cur.reverse().toString() + "0".repeat(zero);
}
private String add(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
StringBuilder res = new StringBuilder();
while (i >= 0 || j >= 0 || carry > 0) {
int n1 = (i >= 0) ? num1.charAt(i) - '0' : 0;
int n2 = (j >= 0) ? num2.charAt(j) - '0' : 0;
int total = n1 + n2 + carry;
res.append(total % 10);
carry = total / 10;
i--;
j--;
}
return res.reverse().toString();
}
}JavaScript
class Solution {
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
multiply(num1, num2) {
if (num1 === "0" || num2 === "0") return "0";
if (num1.length < num2.length) {
return this.multiply(num2, num1);
}
let res = "";
let zero = 0;
for (let i = num2.length - 1; i >= 0; i--) {
const cur = this.mul(num1, num2[i], zero);
res = this.add(res, cur);
zero++;
}
return res;
}
/**
* @param {string} s
* @param {Character} d
* @param {number} zero
* @return {string}
*/
mul(s, d, zero) {
let i = s.length - 1;
let carry = 0;
const digit = Number(d);
let cur = "";
while (i >= 0 || carry) {
const n = i >= 0 ? Number(s[i]) : 0;
const prod = n * digit + carry;
cur = (prod % 10) + cur;
carry = Math.floor(prod / 10);
i--;
}
return cur + "0".repeat(zero);
}
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
add(num1, num2) {
let i = num1.length - 1, j = num2.length - 1, carry = 0;
let res = "";
while (i >= 0 || j >= 0 || carry) {
const n1 = i >= 0 ? Number(num1[i]) : 0;
const n2 = j >= 0 ? Number(num2[j]) : 0;
const total = n1 + n2 + carry;
res = (total % 10) + res;
carry = Math.floor(total / 10);
i--;
j--;
}
return res;
}
}2. Multiplication
Time & Space Complexity
- Time complexity: O(m∗n)
- Space complexity: O(m+n)
Where m is the length of the array queries and n is the length of the array intervals.
C++
Java
Python
JavaScript
C++
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") {
return "0";
}
vector res(num1.length() + num2.length(), 0);
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
for (int i1 = 0; i1 < num1.length(); i1++) {
for (int i2 = 0; i2 < num2.length(); i2++) {
int digit = (num1[i1] - '0') * (num2[i2] - '0');
res[i1 + i2] += digit;
res[i1 + i2 + 1] += res[i1 + i2] / 10;
res[i1 + i2] %= 10;
}
}
stringstream result;
int i = res.size() - 1;
while (i >= 0 && res[i] == 0) {
i--;
}
while (i >= 0) {
result << res[i--];
}
return result.str();
}
}; Java
public class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int[] res = new int[num1.length() + num2.length()];
num1 = new StringBuilder(num1).reverse().toString();
num2 = new StringBuilder(num2).reverse().toString();
for (int i1 = 0; i1 < num1.length(); i1++) {
for (int i2 = 0; i2 < num2.length(); i2++) {
int digit = (num1.charAt(i1) - '0') * (num2.charAt(i2) - '0');
res[i1 + i2] += digit;
res[i1 + i2 + 1] += res[i1 + i2] / 10;
res[i1 + i2] %= 10;
}
}
StringBuilder result = new StringBuilder();
int i = res.length - 1;
while (i >= 0 && res[i] == 0) {
i--;
}
while (i >= 0) {
result.append(res[i--]);
}
return result.toString();
}
}
Python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if "0" in [num1, num2]:
return "0"
res = [0] * (len(num1) + len(num2))
num1, num2 = num1[::-1], num2[::-1]
for i1 in range(len(num1)):
for i2 in range(len(num2)):
digit = int(num1[i1]) * int(num2[i2])
res[i1 + i2] += digit
res[i1 + i2 + 1] += res[i1 + i2] // 10
res[i1 + i2] = res[i1 + i2] % 10
res, beg = res[::-1], 0
while beg < len(res) and res[beg] == 0:
beg += 1
res = map(str, res[beg:])
return "".join(res)JavaScript
class Solution {
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
multiply(num1, num2) {
if (num1 === '0' || num2 === '0') {
return '0';
}
const res = new Array(num1.length + num2.length).fill(0);
num1 = num1.split('').reverse().join('');
num2 = num2.split('').reverse().join('');
for (let i1 = 0; i1 < num1.length; i1++) {
for (let i2 = 0; i2 < num2.length; i2++) {
const digit = parseInt(num1[i1]) * parseInt(num2[i2]);
res[i1 + i2] += digit;
res[i1 + i2 + 1] += Math.floor(res[i1 + i2] / 10);
res[i1 + i2] %= 10;
}
}
let result = '';
let i = res.length - 1;
while (i >= 0 && res[i] === 0) {
i--;
}
while (i >= 0) {
result += res[i--];
}
return result;
}
}
