In the Leetcode Multiply Strings problem solution 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 <= 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
Solution in C Programming
#include<string.h>
struct num
{
int num[10000];
int c;
};
void display(struct num a)
{
int i;
for (i=a.c-1;i>=0;i--)
{
printf("%d",a.num[i]);
}
}
void fill(char *s,struct num *p)
{
int l =strlen( s);
int i;
for ( i=l-1;i>=0;i--)
{
p->num[l-1-i]=s[i]-'0';
}
p->c=l;
}
void right_shift(struct num *a,int x)// x here represents 10's power
{
if (a->num[(a->c-1)]==0)
return;
int i;
for (i=a->c-1;(a->c)-1-i<a->c;i--)
{
a->num[i+x]=a->num[i];
}
while (i+x>=0)
{
a->num[i+x]=0;
i--;
}
a->c=(a->c)+x;
}
struct num * mul( struct num a,int x)
{
struct num * k=(struct num *)malloc(sizeof(struct num ));
k->c=0;
if (x==0) return k;
int carry=0,i;
for (i=0;i<a.c;i++)
{
int t=(a.num[i]*x+carry);
k->num[i]=t%10;
carry=t/10;
}
while(carry>0)
{
k->num[i]=carry%10;
carry/=10;
i++;
}
k->c=i;
return k;
}
void add(struct num *a,struct num * b)
{
int i,carry=0;
//printf("a.c:%d and b.c=%d\n",a->c,b->c);
for(i=0;i<(((a->c)>(b->c))?(a->c):(b->c));i++)
{
//printf("visited i:%d comparison:%d\n",i,((a->c)>(b->c))?(a->c):(b->c));
int aa,bb;
if (i>=a->c)aa=0;
else
aa=a->num[i];
if (i>=b->c)bb=0;
else
bb=b->num[i];
int t=aa+bb+carry;
carry=t/10;
a->num[i]=t%10;
}
while( carry)
{
a->num[i]=carry%10;
carry/=10;
i++;
}
a->c=i;
}
char s[10000];
char* multiply(char* num1, char* num2) {
struct num n1,n2;
fill(num1,&n1);
fill(num2,&n2);
struct num ans;
ans.c=0;
int i;
for ( i=0;i<n2.c;i++)
{
if (n2.num[i]==0) continue;
struct num *p=mul(n1,n2.num[i]);
right_shift(p,i);
add(&ans,p);
free(p);
}
for ( i=0;i<ans.c;i++)
{
s[i]=ans.num[(ans.c)-i-1]+'0';
}
if (ans.c==0)
{
s[0]='0';
i=1;
}
//printf("i:%d",i);
s[i]='\0';
return s;
}Solution in C++ Programming
class Solution {
public:
string multiply(string num1, string num2) {
vector<string> v;
if(num1[0]=='0' || num2[0]=='0' )
{
return "0";
}
if(num1.size()>num2.size())
{
string xx=num2;
num2=num1;
num1=xx;
}
for(int i=num1.size()-1;i>=0;i--)
{
int c=0;
string y="";
for(int j=num2.size()-1;j>=0;j--)
{
int m=(num1[i]-'0')*(num2[j]-'0')+c;
c=m/10;
m=m%10;
y=to_string(m)+y;
}
if(c>0)
{
y=to_string(c)+y;
}
v.push_back(y);
}
string x=v[0];
for(int i=1;i<v.size();i++)
{
string y="";
int k=v[i].size()-1;
int c=0;
for(int j=x.size()-1;j>=0;j--)
{
if(j>(x.size()-1-i))
{
y=x[j]+y;
}
else if(k>=0)
{
int m=(x[j]-'0')+(v[i][k]-'0')+c;
cout<<m<<" ";
c=m/10;
m=m%10;
y=to_string(m)+y;
k--;
}
}
for(int j=k;j>=0;j--)
{
int m=(v[i][j]-'0')+c;
c=m/10;
m=m%10;
y=to_string(m)+y;
}
if(c>0)
{
y=to_string(c)+y;
}
x=y;
}
return x;
}
};Solution in Java Programming
public String multiply(String num1, String num2) {
int[] ans = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
for (int j = num2.length() - 1; j >= 0; j--) {
ans[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
ans[i + j] += ans[i + j + 1] / 10;
ans[i + j + 1] = ans[i + j + 1] % 10;
}
}
int i = 0;
while (i < ans.length && ans[i] == 0) {
i++;
}
StringBuilder sb = new StringBuilder();
while (i < ans.length) {
sb.append(ans[i]);
i++;
}
return sb.length() == 0 ? "0" : sb.toString();
}Solution in Python Programming
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1 = num1[::-1]
num2 = num2[::-1]
result = [0 for i in range(len(num1)+len(num2))]
for i in range(len(num1)):
for j in range(len(num2)):
result[i+j] += int(num1[i]) * int(num2[j])
for i in range(len(result)):
if result[i] >= 10:
result[i+1] += result[i] // 10
result[i] = result[i] % 10
result = result[::-1]
while result[0] == 0 and len(result) > 1:
del result[0]
final = ''.join(map(str, result))
return finalSolution in C# Programming
public class Solution
{
public string Multiply(string num1, string num2)
{
List<string> individualResults = new List<string>();
for (int i = num2.Length - 1; i >= 0; i--)
{
char[] zeroCharArr = new char[num2.Length-1-i];
for (int j = 0; j < zeroCharArr.Length; j++)
zeroCharArr[j] = '0';
string zeroPadding = new string(zeroCharArr);
string result = Multiply(num1, num2[i], zeroPadding);
individualResults.Add(result);
}
string totalResult =
BinaryAddStrings(individualResults, 0, individualResults.Count - 1);
totalResult = totalResult.TrimStart('0');
if(totalResult == "") return "0";
return totalResult;
}
public string Multiply(string num1, char c, string zeroPadding)
{
int num2Digit = c - '0';
char[] result = new char[num1.Length];
int carry = 0;
for (int i = num1.Length - 1; i >= 0; i--)
{
int num1Digit = num1[i] - '0';
int multRes = num1Digit * num2Digit + carry;
int resDigit = multRes % 10;
carry = multRes / 10;
result[i] = Convert.ToString(resDigit)[0];
}
string finalResult = carry.ToString() + new string(result) + zeroPadding;
finalResult = finalResult.TrimStart('0');
return finalResult;
}
public string BinaryAddStrings(List<string> individualResults, int start, int end)
{
if (start > end)
return "";
if (start == end)
return individualResults[start];
int mid = (start + end) / 2;
string leftSumStr = BinaryAddStrings(individualResults, start, mid);
string rightSumStr = BinaryAddStrings(individualResults, mid + 1, end);
return AddTwoStrings(leftSumStr, rightSumStr);
}
public string AddTwoStrings(string s1, string s2)
{
char[] result = new char[Math.Max(s1.Length, s2.Length) + 1];
for (int i = 0; i < result.Length; i++)
result[i] = '0';
char[] s1Arr = s1.ToCharArray();
char[] s2Arr = s2.ToCharArray();
Array.Reverse(s1Arr);
Array.Reverse(s2Arr);
int carry = 0;
for (int i = 0; i < Math.Max(s1.Length, s2.Length); i++)
{
int s1Int = i < s1.Length ? s1Arr[i] - '0' : 0;
int s2Int = i < s2.Length ? s2Arr[i] - '0' : 0;
int totalSum = s1Int + s2Int + carry;
int sum = totalSum % 10;
carry = totalSum / 10;
result[i] = Convert.ToString(sum)[0];
}
if (carry == 1)
result[result.Length - 1] = '1';
Array.Reverse(result);
string resultStr = new string(result);
resultStr = resultStr.TrimStart('0');
return resultStr;
}
}Also read,