String Multiplication Calculation

For smaller numbers, you can directly use the operators provided by programming languages for calculations. However, if the two factors being multiplied are very large, the data types provided by the language may overflow. An alternative approach is to input the numbers as strings and then mimic the multiplication process we learned in elementary school to calculate 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 cannot directly convert them to integers and perform calculations. The only approach is to mimic manual multiplication.

For example, when manually calculating 123 × 45, you would compute as follows:

Calculate 123 × 5, then 123 × 4, and finally add them with a shift. Even elementary school students can perform this process proficiently, but can you mechanize this calculation process and write a set of algorithmic instructions for a computer to execute?

In this simple process, there are multiplication carry, shifted addition, and addition carry involved. There are also subtle issues, such as the result of multiplying two two-digit numbers can be three or four digits. How would you come up with a standardized handling method? This is the charm of algorithms. Without computational thinking, even simple problems may not be automatically processed.

Firstly, this manual method is still too "advanced." We need to break it down further: the process of 123 × 5 and 123 × 4 can be further decomposed and then added:

Now, 123 is not large, but if it were a very large number, it would be impossible to calculate the product directly. We can use an array to receive the addition results:

The entire calculation process is roughly as follows: two pointers i and j traverse num1 and num2 to compute the product, while adding the product to the correct position in res, as shown in the GIF below:

Now there is a key issue: how to add the product to the correct position in res, or how to compute the corresponding index of res using i and j?

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

Understanding this, you can code to mimic this calculation 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.