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


  • 5
    R
    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;
        }
    };

  • 0
    D

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

  • 0
    D

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


Log in to reply
 

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