LeetCode: Multiply Strings Solution

Approach

Apply this (I don't know what this is called in English so please comment if you know)

1(a + b) * (c + d) = a * c + a * d + b * c + b * d

Example

1123 * 456
2
3123 = 100 + 20 + 3
4456 = 400 + 50 + 6
5
6123 * 456 = (100 + 20 + 3) * (400 + 50 + 6)

For sum, we will use solution from LeetCode 415 Add Strings

For multiplication of numbers like 10 200 3000, etc. Yes we will not use normal multiplication with BigInt since this would violate the problem's rules. Instead, we will do the multiplication for the digit, and add up the rest zeros

Example

1300 * 40000
2
3300:   digit 3, 2 0s
440000: digit 4, 4 0s
5
6300 * 40000 = 3 * 4 + (2 + 4)0s = 12 plus '000000' = 12000000

Implementation

1// this is from LeetCode 415 Add Strings
2var addStrings = function (num1, num2) {
3  const maxLength = Math.max(num1.length, num2.length)
4  num1 = num1.padStart(maxLength, "0").split("").reverse()
5  num2 = num2.padStart(maxLength, "0").split("").reverse()
6
7  const res = []
8  let carry = 0
9
10  for (let i = 0; i < maxLength; i++) {
11    const digitSum = Number(num1[i]) + Number(num2[i]) + carry
12    res.push(digitSum % 10)
13    carry = Math.floor(digitSum / 10)
14  }
15
16  carry && res.push(carry)
17
18  return res.reverse().join("")
19}
20
21const splitToDigitAndZeros = num => {
22  const n = num.length
23  return num.split("").map((digit, i) => [digit, n - i - 1])
24}
25
26var multiply = function (num1, num2) {
27  num1 = splitToDigitAndZeros(num1)
28  num2 = splitToDigitAndZeros(num2)
29
30  let res = "0"
31
32  for (const [digit1, numberOfZeros1] of num1) {
33    for (const [digit2, numberOfZeros2] of num2) {
34      let temp = String(digit1 * digit2)
35      if (temp > 0) temp += "0".repeat(numberOfZeros1 + numberOfZeros2)
36
37      res = addStrings(res, temp)
38    }
39  }
40
41  return String(res)
42}

References

Original problem

Similar problems

Add Two Numbers

Plus One

Add Binary

Add Strings

Apply Discount to Prices