Description: Given two non-negative integers and represented as strings, return the product of and , also represented as a string. num1 num2 num1 num2 You must not use any built-in BigInteger library or convert the inputs to integers directly. Note: Difficulty level: Medium 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 and consist of digits only. num1 num2 Both and do not contain any leading zero, except the number itself. num1 num2 0 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 . 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. here 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 & , the length of the result would be or . For our example length of the result is and is equal to the sum of the lengths of both multipliers . For standardization, we can assume the length of the result is always and sometimes can start with .  For example or m n m + n m + n - 1 5 3 + 2 m + n 0 987 x 43 = 42441 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 and 1 space left to pick , while their multiplication 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 and the index of its selected digit is , accordingly length of the second multiplier is and the index of the digit is . If the first digit is spaces away right border and the second digit is spaces away from the right border, then their multiplication would be 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. 8 4 32 m i n j m-i n-j m+n - (m-i) - (n-j) = i+j Multiplication of digits at index (of the first multiplier) and at index (of the second multiplier) is located at indices & of the result i j i+j i+j+1 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 we can cut return right away saving a bit on unnecessary calculations. ‘0’ ‘0‘ if (num1 === '0' || num2 === '0') return '0' As was mentioned earlier the length of the result is known ( ), so we can do some prep work and create an array and populate it with zeros. m + n const m = num1.length, n = num2.length, res = new Array(m+n).fill(0) To perform the multiplication we iterate and over both multipliers from right to left. Inside the loops, we calculate two indices of the results array that would be affected and . While calculating the it’s important to add to the multiplication of two digits. And  finally, update the r results array at indices and . i j p1 p2 sum res[p2] es p1 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

Read My Stories

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

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

Too Long; Didn't Read

Arman Murzabulatov

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

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

Too Long; Didn't Read

Arman Murzabulatov

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES