Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
Solution:
string multiply(string num1, string num2) {
int s1 = num1.size();
int s2 = num2.size();
string result(s1+s2+1, '0');
std::reverse(num1.begin(),num1.end());
std::reverse(num2.begin(),num2.end());
int digit1 = 0;
int carry = 0;
for(int i =0;i<s1;i++)
{
digit1 = num1[i] - '0';
carry = 0;
for(int j=0;j<s2;j++)
{
int digit2 = num2[j] - '0';
int exist = result[i+j] - '0';
result[i+j] = (digit1*digit2+exist+carry)%10 + '0';
carry = (digit1*digit2+exist+carry)/10;
}
if(carry>0)
{
result[i+s2] = carry+'0';
}
}
std::reverse(result.begin(),result.end());
int start = 0;
while(result[start]=='0'&&start<result.size()) // skip leading '0'
{
start++;
}
if(start == result.size())
return "0";
else
return result.substr(start);
}
No comments:
Post a Comment