Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
分析
两个非负整数相乘，位数小于110位，大整数相乘，每个位对应依次相乘，大于9就进位。结果数组的长度最少是两个因数的总长度加2.一位是进位，另一位是'\0'。
char* multiply(char* num1, char* num2) {
int length1=0,length2=0;
//calculate the length of num1 and num2
while(num1[length1]!='\0')
length1++;
while(num2[length2]!='\0')
length2++;
char *ans=(char *)malloc(sizeof(char)*(length1+length2+2));
for(int i=0;i<length1+length2+1;i++)
ans[i]='0';
ans[length1+length2+1]='\0';
for(int i=0;i<length1;i++)
{
int temp=0;
for(int j=0;j<length2;j++)
{
temp=temp+(num1[length1-i-1]-'0')*(num2[length2-j-1]-'0')+ans[length1+length2-i-j]-'0';
if(temp>9)
{
ans[length1+length2-i-j]=temp%10+'0';
temp=temp/10;
}
else
{
ans[length1+length2-i-j]=temp+'0';
temp=0;
}
}
if(temp>0)
ans[length1+length2-i-length2]=temp+'0';
//printf("%s\n",ans);
}
int anslength=0;
while(ans[anslength]=='0')
anslength++;
if(anslength==length1+length2+1)
return "0";
else
return ans+anslength;
}
