C++ AC solution with explanations and comments, easy to understand.


  • 0
    K

    Renewed solution

    The idea is that to perform multiplication without doing any carry at first but do it later.

    Here is the illustration:

     1  2  3  4
           5  6
    -----------
        6 12 18
     5 10 15  0
    -----------
     5 16 27 18
    

    After this, we can do carry based on the temporary result 5 16 27 18 to 6 8 8 8.

    Then, Convert the vector<int> to string.

    At last, Erase the extra zeros since the buffer's size is x.size() + y.size() which is not necessarily needed.

    Code :


    string multiply(string x, string y) {

        if (x.empty() or y.empty() or x == "0" or y == "0") 
            return "0";
    
        const int max_len = x.size() + y.size();
        vector<int> buffer(max_len, 0);
    
        //-----------------------------------------------------
        // Do multiplication with no carry operations
        for (int i = x.size() - 1; i > -1; --i) 
        {
            for (int j = y.size() - 1; j > -1; --j) 
            {
                int local_result = (x[i] - '0') * (y[j] - '0');
                
                // Here i serves as an offset 
                // with respect to the alignment of local result
                buffer[i + j + 1] += local_result;
            }
        }
    
        //-----------------------------------------------------
        // Perform carry operation
        int carry = 0;
        int digit = 0;
    
        for (int i = max_len - 1; i > -1; --i) 
        {
            digit = (buffer[i] + carry) % 10;
            carry = (buffer[i] + carry) / 10;
            buffer[i] = digit;
        }
    
        //-----------------------------------------------------
        // Convert buffer to string
        string result;
        for (int i = 0; i < max_len; ++i)
            result += to_string(buffer[i]);
        
        //-----------------------------------------------------
        // Erase the extra zeros
        size_t valid_begin = result.find_first_not_of('0');
        result = result.substr(valid_begin);
    
        return result;
    }

Log in to reply
 

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