Algorithm
Problem Name: 43. Multiply Strings
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.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
char* multiply(char* num1, char* num2) {
int l1, l2, l3, *n3, i, j, a, b, x, k;
char *p;
l1 = strlen(num1);
l2 = strlen(num2);
l3 = l1 + l2;
n3 = calloc(l3, sizeof(int));
//assert(n3);
for (i = l1 - 1; i >= 0; i --) {
a = num1[i] - '0';
k = 0; // carry over
for (j = l2 - 1; j >= 0; j --) {
b = num2[j] - '0';
x = n3[i + j + 1] + k + a * b;
k = x / 10;
n3[i + j + 1] = x % 10;
}
n3[i + j + 1] += k;
}
i = 0;
while (i < l3 && !n3[i]) {
i ++;
}
j = 0;
if (i == l3) {
p = malloc(2 * sizeof(char));
//assert(p);
p[j ++] = '0';
} else {
p = malloc((l3 - i + 1) * sizeof(char));
//assert(p);
while (i < l3) {
p[j ++] = '0' + n3[i ++];
}
}
p[j] = 0;
free(n3);
return p;
}
Input
num1 = "2", num2 = "3"
Output
"6"
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0") return "0";
string res = "";
for(int i = num2.size() - 1, zero = 0; i >= 0; i--, zero++)
res=addStr(res, multiStr(num1, num2[i] - '0', zero));
return res;
}
//string * multiple -> string
string multiStr(string s, int multiple, int zero){
int carry = 0;
int n = 0;
for(int i = s.size()-1; i >= 0; i--){
n = (s[i]-'0') * multiple + carry;
s[i] = n%10 + '0';
carry = n/10;
}
if(carry) s = to_string(carry) + s;
while(zero) s += "0", zero--;
return s;
}
//string + string -> string
string addStr(string num1, string num2) {
string s = "";
int carry = 0;
for(int i = num1.size()-1, j = num2.size()-1; i >= 0 || j >= 0 || carry; i--, j--){
int x = i < 0 ? 0 : num1[i] - '0';
int y = j < 0 ? 0 : num2[j] - '0';
s.push_back((x + y + carry) % 10 + '0');
carry = (x + y + carry) / 10;
}
reverse(s.begin(), s.end()>;
return s;
}
};
Input
num1 = "123", num2 = "456"
Output
"56088"
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length();
int n = num2.length();
int[] result = new int[m + n];
int endIdx = m + n - 1;
for (int i = m - 1; i >= 0; i--) {
int resultIdx = endIdx;
int carry = 0;
for (int j = n - 1; j >= 0; j--) {
int currValue = result[resultIdx] + carry + Character.getNumericValue(num1.charAt(i)) * Character.getNumericValue(num2.charAt(j));
carry = currValue / 10;
result[resultIdx--] = currValue % 10;
}
while (carry > 0) {
result[resultIdx--] = carry % 10;
carry /= 10;
}
endIdx--;
}
int idx = 0;
while (idx < result.length && result[idx] == 0) {
idx++;
}
StringBuilder sb = new StringBuilder();
for (int i = idx; i < result.length; i++) {
sb.append(result[i]);
}
return sb.length() == 0 ? "0" : sb.toString();
}
}
Input
num1 = "2", num2 = "3"
Output
"6"
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const multiply = function(num1, num2) {
let m = num1.length,
n = num2.length;
let pos = new Array(m + n).fill(0);
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
let mul = (num1.charAt(i) - "0") * (num2.charAt(j) - "0");
let p1 = i + j,
p2 = i + j + 1;
let sum = mul + pos[p2];
pos[p1] += Math.floor(sum / 10);
pos[p2] = sum % 10;
}
}
let str = "";
for (let p of pos) if (!(str.length === 0 && p === 0)) str += p;
return str.length === 0 ? "0" : str;
};
Input
num1 = "123", num2 = "456"
Output
"56088"
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def multiply(self, num1, num2):
dic, l1, l2 = {str(i): i for i in range(10)}, len(num1) - 1, len(num2) - 1
return str(sum([dic[n1] * (10**(l1-i)) for i, n1 in enumerate(num1)]) * sum([dic[n2] * (10**(l2-j)) for j, n2 in enumerate(num2)]))
Input
num1 = "2", num2 = "3"
Output
6
#6 Code Example with C# Programming
Code -
C# Programming
using System.Text;
namespace LeetCode
{
public class _043_MultiplyStrings
{
public string Multiply(string num1, string num2)
{
if (num1 == "0" || num2 == "0") { return "0"; }
var MAX_RADIX = 1000000000;
var RADIX_LENGTH = 9;
var num1Value = new long[num1.Length / RADIX_LENGTH + 1];
var num2Value = new long[num2.Length / RADIX_LENGTH + 1];
int i, j, temp, data, index = 0;
for (i = num1.Length; i > 0; i -= RADIX_LENGTH)
{
data = 0;
temp = i > RADIX_LENGTH ? i - RADIX_LENGTH : 0;
for (j = temp; j < i; j++)
{
data = data * 10 + (num1[j] - '0');
}
num1Value[index++] = data;
}
index = 0;
for (i = num2.Length; i > 0; i -= RADIX_LENGTH)
{
data = 0;
temp = i > RADIX_LENGTH ? i - RADIX_LENGTH : 0;
for (j = temp; j < i; j++)
{
data = data * 10 + (num2[j] - '0');
}
num2Value[index++] = data;
}
var resultValue = new long[num1Value.Length + num2Value.Length];
for (i = 0; i < num1Value.Length; i++)
{
for (j = 0; j < num2Value.Length; j++)
{
resultValue[i + j] += num1Value[i] * num2Value[j];
if (resultValue[i + j] >= MAX_RADIX)
{
resultValue[i + j + 1] += resultValue[i + j] / MAX_RADIX;
resultValue[i + j] = resultValue[i + j] % MAX_RADIX;
}
}
}
var builder = new StringBuilder();
var tempStr = string.Empty;
var started = false;
for (i = resultValue.Length - 1; i >= 0; i--)
{
if (resultValue[i] != 0)
{
tempStr = resultValue[i].ToString();
if (started)
{
builder.Append('0', 9 - tempStr.Length);
}
builder.Append(resultValue[i].ToString());
started = true;
}
}
return builder.ToString();
}
}
}
Input
num1 = "123", num2 = "456"
Output
"56088"