# Simplified c++ solution, O(n*(n+m)), 13 lines

• ``````class Solution {
public:
string multiply(string num1, string num2) {
int l1 = num1.length(), l2=num2.length(),carry = 0;;
if(num1=="0" || num2=="0") return "0";
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
string res(l1+l2,0);
for(int len=1; len<=l1+l2; ++len){
for(int i=0; i<len&&i<l1; ++i){
if(len-i-1 <l2) carry += (num1[i]-'0')*(num2[len-i-1]-'0');
}
res[len-1]=(carry%10)+'0';
carry /= 10;
}
if(res[res.length()-1]=='0') res.pop_back();
reverse(res.begin(), res.end());
return res;
}
};``````

• It's O(nm) solution. Only you need is modify internal loop like this. In this case carry would be evaluated exactly nm times. Here is picture. j=len-i-1, internal square represent loop, numbers in square are len-1.

``````    // i=  2  1  0  n2 j
// n1= 2  3  4   = =
//
//     5  4  3   6 3
//     4  3  2   7 2
//     3  2  1   8 1
//     2  1  0   9 0

for(int i=max(len-l2, 0); i<len&&i<l1; ++i){
carry += (num1[i]-'0')*(num2[len-i-1]-'0');
}
``````

• more to say, we could have overflow in 'carry' variable

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.