Solution
Approach 1
A straightforward approach is to multiply as we do normally without any optimisation. We follow this procedure:
num1 = 123
num2 = 456
123
x 456
-------
738 // 6*123
+ 615 // 5*123
+ 492 // 4*123
-------
56088
-------
But this requires both multiplication of a string and addition of two strings so this can be very time taking.
string multiply(string num1, string num2) {
int carry = 0, n1, n2;
string res = "";
// sanity check
if (num1=="0" || num2=="0")
return "0";
for (int i=num1.size()-1, k=0; i>=0; i--, k++) {
string temp = "";
for (int l=0; l<k; l++)
temp+='0';
for (int j=num2.size()-1; j>=0; j--) {
n1 = num2[j]-'0';
n2 = num1[i]-'0';
temp += (n1*n2+carry)%10+'0';
carry = (n1*n2+carry)/10;
}
if (carry)
temp += carry+'0';
carry = 0;
reverse(temp.begin(), temp.end());
res = addStrings(res, temp);
}
return res;
}
string addStrings(string num1, string num2) {
string ans = "";
int carry = 0;
for (int i=num1.length()-1, j=num2.length()-1; i>=0 || j>=0; i--, j--) {
int n1 = i < 0 ? 0 : num1[i]-'0';
int n2 = j < 0 ? 0 : num2[j]-'0';
ans += (n1 + n2 + carry) % 10 + '0';
carry = (n1 + n2 + carry)/10;
}
if (carry)
ans += '1';
reverse(begin(ans), end(ans));
return ans;
}
Approach 2
As mentioned by ChiangKaiShrek, this is the standard manual multiplication algorithm. We use two nested for loops, working backward from the end of each input number. We pre-allocate our result and accumulate our partial result in there. One special case to note is when our carry requires us to write to our sum string outside of our for loop.
At the end, we trim any leading zeros, or return 0 if we computed nothing but zeros.
string multiply(string num1, string num2) {
string sum(num1.size() + num2.size(), '0');
for (int i = num1.size() - 1; 0 <= i; --i) {
int carry = 0;
for (int j = num2.size() - 1; 0 <= j; --j) {
int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
sum[i + j + 1] = tmp % 10 + '0';
carry = tmp / 10;
}
sum[i] += carry;
}
for (int i=0; i<sum.size(); i++) {
if (sum[i]!='0')
return sum.substr(i);
}
return "0";
}
Try applying this approach by using 123*456 as an example and it should be pretty clear!