Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Constraints:
1 <= num1.length, num2.length <= 200num1andnum2consist of digits only.- Both
num1andnum2do not contain any leading zero, except the number0itself.
Solution 1: Simulating Mathematical Multiplication
Assume the lengths of
The proof is as follows:
- If
$num1$ and$num2$ both take the minimum value, then their product is${10}^{m - 1} \times {10}^{n - 1} = {10}^{m + n - 2}$ , with a length of$m + n - 1$ . - If
$num1$ and$num2$ both take the maximum value, then their product is$({10}^m - 1) \times ({10}^n - 1) = {10}^{m + n} - {10}^m - {10}^n + 1$ , with a length of$m + n$ .
Therefore, we can apply for an array of length
From the least significant digit to the most significant digit, we calculate each digit of the product in turn, and finally convert the array into a string.
Note to check whether the most significant digit is
The time complexity is
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
arr = [0] * (m + n)
for i in range(m - 1, -1, -1):
a = int(num1[i])
for j in range(n - 1, -1, -1):
b = int(num2[j])
arr[i + j + 1] += a * b
for i in range(m + n - 1, 0, -1):
arr[i - 1] += arr[i] // 10
arr[i] %= 10
i = 0 if arr[0] else 1
return "".join(str(x) for x in arr[i:])class Solution {
public String multiply(String num1, String num2) {
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
int m = num1.length(), n = num2.length();
int[] arr = new int[m + n];
for (int i = m - 1; i >= 0; --i) {
int a = num1.charAt(i) - '0';
for (int j = n - 1; j >= 0; --j) {
int b = num2.charAt(j) - '0';
arr[i + j + 1] += a * b;
}
}
for (int i = arr.length - 1; i > 0; --i) {
arr[i - 1] += arr[i] / 10;
arr[i] %= 10;
}
int i = arr[0] == 0 ? 1 : 0;
StringBuilder ans = new StringBuilder();
for (; i < arr.length; ++i) {
ans.append(arr[i]);
}
return ans.toString();
}
}class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") {
return "0";
}
int m = num1.size(), n = num2.size();
vector<int> arr(m + n);
for (int i = m - 1; i >= 0; --i) {
int a = num1[i] - '0';
for (int j = n - 1; j >= 0; --j) {
int b = num2[j] - '0';
arr[i + j + 1] += a * b;
}
}
for (int i = arr.size() - 1; i; --i) {
arr[i - 1] += arr[i] / 10;
arr[i] %= 10;
}
int i = arr[0] ? 0 : 1;
string ans;
for (; i < arr.size(); ++i) {
ans += '0' + arr[i];
}
return ans;
}
};func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
m, n := len(num1), len(num2)
arr := make([]int, m+n)
for i := m - 1; i >= 0; i-- {
a := int(num1[i] - '0')
for j := n - 1; j >= 0; j-- {
b := int(num2[j] - '0')
arr[i+j+1] += a * b
}
}
for i := len(arr) - 1; i > 0; i-- {
arr[i-1] += arr[i] / 10
arr[i] %= 10
}
i := 0
if arr[0] == 0 {
i = 1
}
ans := []byte{}
for ; i < len(arr); i++ {
ans = append(ans, byte('0'+arr[i]))
}
return string(ans)
}function multiply(num1: string, num2: string): string {
if ([num1, num2].includes('0')) return '0';
const n1 = num1.length,
n2 = num2.length;
let ans = '';
for (let i = 0; i < n1; i++) {
let cur1 = parseInt(num1.charAt(n1 - i - 1), 10);
let sum = '';
for (let j = 0; j < n2; j++) {
let cur2 = parseInt(num2.charAt(n2 - j - 1), 10);
sum = addString(sum, cur1 * cur2 + '0'.repeat(j));
}
ans = addString(ans, sum + '0'.repeat(i));
}
return ans;
}
function addString(s1: string, s2: string): string {
const n1 = s1.length,
n2 = s2.length;
let ans = [];
let sum = 0;
for (let i = 0; i < n1 || i < n2 || sum > 0; i++) {
let num1 = i < n1 ? parseInt(s1.charAt(n1 - i - 1), 10) : 0;
let num2 = i < n2 ? parseInt(s2.charAt(n2 - i - 1), 10) : 0;
sum += num1 + num2;
ans.unshift(sum % 10);
sum = Math.floor(sum / 10);
}
return ans.join('');
}function multiply(num1: string, num2: string): string {
if (num1 === '0' || num2 === '0') {
return '0';
}
const n = num1.length;
const m = num2.length;
const res = [];
for (let i = 0; i < n; i++) {
const a = Number(num1[n - i - 1]);
let sum = 0;
for (let j = 0; j < m || sum !== 0; j++) {
const b = Number(num2[m - j - 1] ?? 0);
sum += a * b + (res[i + j] ?? 0);
res[i + j] = sum % 10;
sum = Math.floor(sum / 10);
}
}
return res.reverse().join('');
}impl Solution {
pub fn multiply(num1: String, num2: String) -> String {
if num1 == "0" || num2 == "0" {
return String::from("0");
}
let (num1, num2) = (num1.as_bytes(), num2.as_bytes());
let (n, m) = (num1.len(), num2.len());
let mut res = vec![];
for i in 0..n {
let a = num1[n - i - 1] - b'0';
let mut sum = 0;
let mut j = 0;
while j < m || sum != 0 {
if i + j == res.len() {
res.push(0);
}
let b = num2.get(m - j - 1).unwrap_or(&b'0') - b'0';
sum += a * b + res[i + j];
res[i + j] = sum % 10;
sum /= 10;
j += 1;
}
}
res.into_iter()
.rev()
.map(|v| char::from(v + b'0'))
.collect()
}
}