My code gives Wrong output for a very large input? What is wrong?


#1

Wrong ans for
A “5131848155574784703269632922904933776792735241197982102373370” B “56675688419586288442134264892419611145485574406534291250836”.

Can someone tell me what is wrong with my code?

string add(string ans, string prev)
{
int n = ans.size(), m = prev.size();
if(n> m)
{
while(n > m)
{
prev+= ‘0’ ;
m++;
}
}
n = ans.size();
m = prev.size();
//cout<<“ans = “<<ans<<” prev= “<<prev<<” “;
string s =””;
int carry = 0;
for(int i = 0 ; i < n; i++)
{
s+=to_string(((ans[i] - ‘0’)+(prev[i] - ‘0’) + carry)%10);
//cout<<"S = “<<s<<” ";

        carry = ((ans[i] - '0')+(prev[i] - '0'))/10;
        //cout<<"carry = "<<carry<<" ";
    //}
}
if(carry)
{
    s += to_string(carry);
}
//cout<<"s = "<<s<<" " ;
return s;

}

string Solution::multiply(string A, string B) {

int m = A.size(), n = B.size();
int x =0;
while(A[x] == '0')
{
    A.erase(A.begin());
    x++;
}
x = 0;
while(B[x] == '0')
{
    B.erase(B.begin());
    x++;
}
 m = A.size();
 n = B.size();
if(n == 0 || m == 0)    return "0";
if(n > m)
{
    return multiply(B, A);
}
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
string prev = "";
for(int i = 0 ; i < n; i++)
{
    string ans= "";
    int c = 0;
    for(int j = 0 ; j < m; j++)
    {
        int a = (A[j] -'0') * (B[i] - '0');
        int b = (a+c)%10;
        ans += to_string(b); 
        //cout<<"ans = "<<ans<<" ";
        if((A[i] -'0') * (B[i] - '0') > 9){
        c = (A[i] -'0') * (B[i] - '0');
        c = c/10;
        }
    }
    if(c)
    {
        ans += (c + '0') ;
        c  = 0;
    }
    for(int n = 0; n < i; n++)
    {
        ans = '0' + ans;
    }
    //cout<<"after 1 digit multiplication "<<ans<<" ";
    if(i ==0 )  prev = ans;
    else
    {
        prev = add(ans, prev);
    }
    //cout<<"prev after addition is "<<prev<<" ";
}
//cout<<"prev = "<<prev<<" ";
reverse(prev.begin(), prev.end());
//cout<<"reversed  = ";
//cout<<"prev = "<<prev<<" ";
int i = 0;
while(prev[i] == '0')
{
    prev.erase(prev.begin());
}
return prev;

}


#2

I’m quite late to this, But I was stuck on the same test case for a long time :smiley:
In your code, you aren’t updating the carry appropriately in your add function:

 carry = ((ans[i] - '0')+(prev[i] - '0'))/10;

should be

 carry = ((ans[i] - '0')+(prev[i] - '0') + carry)/10;

#3

You can try this: