My concise 9ms C++ solution


  • 0
    M

    First,multiply each numbers directly and store the value into array,
    Second,if the value in the result array is >10, generate carry to
    the next element of the result array.
    Third, reverse the result array and erase the preceding zeros.

    string multiply(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        if (num1 == "0" || num2 == "0") return "0";
        vector<int> res(m+n, 0);
        reverse(begin(num1),end(num1));
        reverse(begin(num2),end(num2));
        for (int i = 0; i < n; ++i) 
            for (int idx = i, j = 0; j < m; ++j)
                res[idx++] += (num2[i]-'0')*(num1[j]-'0'); 
        
        int carry = 0;
        for (int i = 0; i < m+n; ++i) {
            int tmp = res[i];
            res[i] = (tmp+carry)%10; 
            carry = (tmp+carry)/10;
        }
        
        string str(m+n,'0');
        for (int k = 0, i = res.size()-1; i >= 0; --i) str[k++] = res[i]+'0';
        auto idx = str.find_first_not_of('0');
        return str.substr(idx);
    }

Log in to reply
 

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