Multiply Strings (LeetCode): An Out of the Box Solution In JavaScript

Description:

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integers directly.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Reasoning:

This classic problem has been solved many times using different approaches. A full description of most of the standard solutions can be found among official Leetcode solutions here. However, there is one out-of-the-box solution that is easy to understand and quick to implement. The solution was originally posted in the discussion section and became the most-voted Java solution. In this short article, I’ll explain the reasoning and provide the solution written in JavaScript.

Let’s review the multiplication process we all used to perform when we were at school. We perform the multiplication for every pair of digits from right to left and then perform multiplication as shown in the picture below.

Let’s observe some of the regularities here. Let’s look at both multipliers and the result as if they were arrays of digits. The first thing we notice is that the length of the result is never greater than the sum of the lengths of both multipliers. If lengths of multipliers are m & n, the length of the result would be m + n or m + n - 1 . For our example length of the result is 5 and is equal to the sum of the lengths of both multipliers 3 + 2. For standardization, we can assume the length of the result is always m + n and sometimes can start with 0. For example 987 x 43 = 42441 or 123 x 45 = 05535.

Another pattern that we can notice is that the more we move left while picking a pair of digits the more their multiplication moves left. From the picture below, we moved 1 space left to pick 8 and 1 space left to pick 4, while their multiplication 32 moved 2 (1+1) spaces left. Let’s try to make a mathematical formula out of this pattern. Assuming the length of the first multiplier is m and the index of its selected digit is i, accordingly length of the second multiplier is n and the index of the digit is j. If the first digit is m-i spaces away right border and the second digit is n-j spaces away from the right border, then their multiplication would be m+n - (m-i) - (n-j) = i+j spaces away from the right border of the result. Take into account zero-based numbering of arrays (indices start from 0 rather than 1) in most modern programming languages.

Multiplication of digits at index i (of the first multiplier) and at index j (of the second multiplier) is located at indices i+j & i+j+1 of the result

Solution:

Let’s try to jump into the implementation and write some JavaScript. First thing is to consider the edge cases. When one of the multipliers is ‘0’ we can cut return ‘0‘ right away saving a bit on unnecessary calculations.

if (num1 === '0' || num2 === '0') return '0'

As was mentioned earlier the length of the result is known (m + n), so we can do some prep work and create an array and populate it with zeros.

const m = num1.length, n = num2.length, res = new Array(m+n).fill(0)

To perform the multiplication we iterate i and j over both multipliers from right to left. Inside the loops, we calculate two indices of the results array that would be affected p1 and p2. While calculating the sum it’s important to add res[p2] to the multiplication of two digits. And finally, update the res results array at indices p1 and p2.

for (let i=m-1; i>=0; i--) {
    for (let j=n-1; j>=0; j--) {

        const p1=i+j, p2=i+j+1

        let sum = res[p2] + Number(num1[i]) * Number(num2[j])
        res[p2] = sum%10
        res[p1] += Math.floor(sum/10)
    }
}

As a final step we get rid of a ‘0’ in it’s present in the beginning and convert results array into a string. So the final code would look like the one below.

var multiply = function(num1, num2) {
    if (num1 === '0' || num2 === '0') return '0'
    
    const m = num1.length, n = num2.length, res = new Array(m+n).fill(0)
    
    for (let i=m-1; i>=0; i--) {
        for (let j=n-1; j>=0; j--) {
            const p1=i+j, p2=i+j+1
            let sum = res[p2] + Number(num1[i]) * Number(num2[j])
            res[p2] = sum%10
            res[p1] += Math.floor(sum/10)
        }
    }
    if (res[0] === 0) res.shift()
    return res.join('')
    
}

The code above has average stats in terms of performance, but is very optimal in terms of memory usage. It has m x n time complexity, where m and n are lengths of inputs.

Lead image by BIG MOUTH for Quanta Magazine