String Multiplication Calculation

For smaller numbers, calculations can directly use the operators provided by programming languages. However, if the two factors being multiplied are very large, the data types provided by the language might overflow. An alternative approach is to input the numbers as strings, then emulate the multiplication process we learned in elementary school to compute the result, also represented as a string.

Consider LeetCode Problem 43, "Multiply Strings":

Input: num1 = "2", num2 = "3"
Output: "6"

Input: num1 = "123", num2 = "456"
Output: "56088"

It's important to note that num1 and num2 can be very long, so you should not directly convert them to integers for computation. The only viable approach is to mimic manual multiplication.

For example, if we manually calculate 123 × 45, it would proceed as follows:

Calculate 123 × 5, then 123 × 4, and finally add them with a shift. This process might be familiar to elementary students, but can you mechanize this multiplication process and write a set of algorithmic instructions for a computer, which has no intelligence, to execute?

Notice that this simple process involves multiplication carry, shifted addition, and addition carry. There are also subtle issues, such as when multiplying two-digit numbers, the result might be three or four digits. How can you devise a standardized approach to handle this? This is the allure of algorithms; without computational thinking, even simple problems might be difficult to automate.

First, this manual method is still too "advanced." We need to break it down further, so the process of 123 × 5 and 123 × 4 can be decomposed into smaller steps and then summed:

123 is not large, but for very large numbers, direct multiplication of the entire number isn't feasible. We can use an array to store the addition results at the bottom:

The entire computational process is roughly as follows: there are two pointers, i and j, traversing num1 and num2, calculating products, and piling the products onto the correct positions in res, as shown in the GIF below:

Now there's a critical question: how to pile the products onto the correct positions in res, or rather, how to determine the corresponding index in res using i and j?

With careful observation, you will find that the product of num1[i] and num2[j] corresponds to the positions res[i+j] and res[i+j+1].

Once you understand this, you can use code to emulate this computational process:

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        // the result can be at most m + n digits
        int[] res = new int[m + n];
        // start multiplying from the least significant digit
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                // the product is at the corresponding index in res
                int p1 = i + j, p2 = i + j + 1;
                // add to res
                int sum = mul + res[p2];
                res[p2] = sum % 10;
                res[p1] += sum / 10;
            }
        }
        // the leading zeros that might exist in the result (unused digits)
        int i = 0;
        while (i < res.length && res[i] == 0)
            i++;
        // convert the calculation result to a string
        StringBuilder str = new StringBuilder();
        for (; i < res.length; i++)
            str.append(res[i]);
        
        return str.length() == 0 ? "0" : str.toString();
    }
}

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        // the result can have at most m + n digits
        vector<int> res(m + n);
        // start multiplying from the least significant digit
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                // the product is at the corresponding index in res
                int p1 = i + j, p2 = i + j + 1;
                // add to res
                int sum = mul + res[p2];
                res[p2] = sum % 10;
                res[p1] += sum / 10;
            }
        }
        // there may be leading zeros in the result (unused digits)
        int i = 0;
        while (i < res.size() && res[i] == 0)
            i++;
        // convert the calculation result to a string
        string str;
        for (; i < res.size(); i++)
            str.push_back(res[i]+'0');
        
        return str.empty() ? "0" : str;
    }
};

class Solution:
    def multiply(self, num1, num2):
        m, n = len(num1), len(num2)
        # the result can have at most m + n digits
        res = [0] * (m + n)
        # start multiplying from the least significant digit
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                # the product is at the corresponding index in res
                p1, p2 = i + j, i + j + 1
                # add to res
                summ = mul + res[p2]
                res[p2] = summ % 10
                res[p1] += summ // 10
        # there may be leading zeros in the result (unused digits)
        i = 0
        while i < len(res) and res[i] == 0:
            i += 1
        # convert the calculation result to a string
        str_res = ''.join(str(x) for x in res[i:])
        
        return "0" if not str_res else str_res

func multiply(num1 string, num2 string) string {
    m, n := len(num1), len(num2)
    // the result can have at most m + n digits
    res := make([]int, m + n)
    
    // start multiplying from the least significant digit
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            mul := int(num1[i] - '0') * int(num2[j] - '0')

            // the product is at the corresponding index in res
            p1, p2 := i + j, i + j + 1
            
            // add to res
            sum := mul + res[p2]
            res[p2] = sum % 10
            res[p1] += sum / 10
        }
    }
    
    // possible leading zeros in the result (unused digits)
    i := 0
    for i < len(res) && res[i] == 0 {
        i++
    }
    
    // convert the calculation result to a string
    var str strings.Builder
    for ; i < len(res); i++ {
        str.WriteString(strconv.Itoa(res[i]))
    }
    
    if str.String() == "" { 
        return "0"
    }

    return str.String()
}

var multiply = function(num1, num2) {
    let m = num1.length, n = num2.length;
    // the result can have at most m + n digits
    let res = new Array(m + n).fill(0);
    // start multiplying from the least significant digit
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            let mul = (num1[i] - '0') * (num2[j] - '0');
            // the product is at the corresponding index in res
            let p1 = i + j, p2 = i + j + 1;
            // add to res
            let sum = mul + res[p2];
            res[p2] = sum % 10;
            res[p1] += Math.floor(sum / 10);
        }
    }
    // the leading zeros in the result (unused digits)
    let i = 0;
    while (i < res.length && res[i] == 0)
        i++;
    // convert the calculation result to a string
    let str = "";
    for (; i < res.length; i++)
        str += res[i];
    
    return str.length == 0 ? "0" : str;
}

Here, we have completed the string multiplication algorithm.

To summarize, some of the ways of thinking that we take for granted are actually very difficult for computers to achieve. For example, our usual arithmetic process is not complicated, but translating it into code logic is not simple. Algorithms need to simplify the calculation process, obtaining results through a method of calculating and accumulating simultaneously.

Proverbs teach us not to fall into fixed patterns of thinking, to avoid being procedural, and to think creatively. However, I believe that being procedural is not necessarily a bad thing; it can greatly improve efficiency and reduce the rate of errors. Isn't an algorithm a set of procedural thinking? Only through procedural methods can we enable computers to help us solve complex problems!

Perhaps algorithms are a kind of thinking that seeks fixed patterns of thought. I hope this article has been helpful to you.