How to Answer: How do you multiply strings without a leading-zero product?
Advice and answer examples written specifically for a JavaScript Intermediate Level Implementation job interview.
2. How do you multiply strings without a leading-zero product?
This question focuses on JavaScript iteration.
You are given two non-negative integers num1 and num2 in the form of strings. Your task is to find the product of num1 and num2 and return it in the form of a string. You can neither use in-built like BigIntger nor convert the numbers from strings to integers. The product must not have any leading zeros.
/*Example*/
Given num1 = “123†num2 = “45â€
Expected output:- “5535â€Solution:
To solve this problem, we need to see how multiplication is done on pen-paper (focus on underlined digits). Let resultString be the resulting number in the form of string.
num1 = 1 2 3 index i of num1 (here i = 1)
num2 = 4 5 index j of num2 (here j = 0)
_______________________
1 5
1 0
0 5
1 2
0 8 index (i + j) and (i + j + 1)
0 4 of resultString (here 1 & 2)
______________________________
0 5 5 3 5
0 1 2 3 4 indices of resultString
It can be observed that the product of digits at indices i and j of num1 and num2 respectively is added to the indices (i + j) and (i + j + 1) of resultString. So we will iterate over each digit of the two numbers starting from unit places (that is we loop in reverse order) and find the product of the digits and store them at the appropriate location. To store the product of the digits, we use a result array. It can be observed that when two integers with digits count m and n are multiplied, the product has at most m + n number of digits.
We use the parseInt function to convert a digit into number form which is in string form initially. Thus parseInt(“2â€) = 2.
After looping over all the digits, the result may have leading zeros. So we loop over the result array and put undefined in place of leading zeroes. Then we use Array.prototype.join method to join the result to form a string which will be our desired result. One thing to note is that the Array.prototype.join method does not take undefined values into account. Thus:
[8, 1].join(“â€) = “81â€
[undefined, 5, 5, 3, 5].join(“â€) = “5535â€
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
function multiply(num1, num2) {
const m = num1.length
const n = num2.length
const result = new Array(m + n).fill(0)
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
const digit1 = parseInt(num1[i])
const digit2 = parseInt(num2[j])
const idx1 = i + j
const idx2 = i + j + 1
const mul = digit1 * digit2
const sum = mul + result[idx2]
result[idx1] += Math.floor(sum / 10)
result[idx2] = sum % 10
}
}
for (let i = 0; i < result.length; i++) {
if (result[i] !== 0) break
result[i] = undefined
}
const resultString = result.join("")
return resultString || "0"
}m = length of num1
n = length of num2
Time complexity- O(m * n)
Space complexity- O(m + n)
Written by S. Kumar on June 27th, 2021