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;
}