4.28.7 — Multiply Strings

LeetCode 43 · Medium

The problem

Multiply two non-negative numbers given as strings, and return the product as a string. You may not convert them to integers or use a big-integer library.

"2", "3"       →  "6"
"123", "456"   →  "56088"

Up to 200 digits each.

The pattern

Long multiplication, as taught in school — but instead of writing down partial products and adding them up, accumulate everything into one array.

The index formula is the whole problem:

Multiplying digit i of num1 by digit j of num2 contributes to positions i + j and i + j + 1 of the result.

Both indices count from the left, and the result array has length m + n.

Why i + j and i + j + 1. Digit i from the left of an m-digit number has place value 10^{m-1-i}. Multiplying two such digits gives place value 10^{(m-1-i) + (n-1-j)} = 10^{(m+n-2) - (i+j)} — which is position i + j + 1 in an array of length m + n, counting from the left. The carry goes one position further left, at i + j.

Check it on the smallest case rather than trusting the algebra. "12" × "34": the last digits are i = 1 and j = 1, giving i + j + 1 = 3 — the final position of a 4-length array ✓.

The maximum product length

Two numbers of m and n digits multiply to at most m + n digits, and at least m + n − 1. So allocate m + n and strip at most one leading zero at the end.

99 × 99 = 9801 — four digits from two twos. 10 × 10 = 100 — three digits, so one leading zero to strip.

The solution

Python

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"                                    # avoids "000"

        m, n = len(num1), len(num2)
        result = [0] * (m + n)

        for i in range(m - 1, -1, -1):                    # right to left
            for j in range(n - 1, -1, -1):
                product = int(num1[i]) * int(num2[j])
                total = product + result[i + j + 1]       # add what is already there

                result[i + j + 1] = total % 10            # keep the units digit
                result[i + j] += total // 10              # carry left

        # strip a single leading zero if present
        start = 1 if result[0] == 0 else 0
        return ''.join(map(str, result[start:]))

TypeScript

function multiply(num1: string, num2: string): string {
  if (num1 === "0" || num2 === "0") return "0";

  const m = num1.length, 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 product = Number(num1[i]) * Number(num2[j]);
      const total = product + result[i + j + 1];

      result[i + j + 1] = total % 10;
      result[i + j] += Math.floor(total / 10);
    }
  }

  const start = result[0] === 0 ? 1 : 0;
  return result.slice(start).join('');
}

Four details, and each one is load-bearing.

result[i + j + 1] is added to, not overwritten. Several digit pairs land on the same position, and they all have to accumulate.

result[i + j] += uses += too, for the same reason — a carry adds to whatever is already waiting there.

The carry is added into position i + j without immediately normalising it. That position may temporarily hold a value above 9, and that is fine: it gets normalised when the loops reach it, because i + j for the current pair is i' + j' + 1 for the pair one step to the left. The right-to-left loop order is what guarantees that.

The zero check at the top prevents "0" × "123" producing a string of zeros.

Only one leading zero can ever appear, because the product has at least m + n − 1 digits — so a single conditional strip is enough, not a loop.

Trace

"12" × "34", result of length 4.

i	j	digits	product	position	after
1	1	2 × 4	8	result[3]	[0,0,0,8]
1	0	2 × 3	6	result[2]	[0,0,6,8]
0	1	1 × 4	4	result[2] → 10	[0,1,0,8] — carry to result[1]
0	0	1 × 3	3, plus the 1 already there = 4	result[1]	[0,4,0,8]

Strip the leading zero → "408" ✓ (12 × 34 = 408).

Notice step 3: the 10 was split into a 0 in place and a 1 carried left, and step 4 then added to that carry. That is why += is required.

Complexity

O(mn) time — every pair of digits is multiplied once. O(m + n) space.

Faster algorithms exist, and naming one is a good finish:

• Karatsuba — O(n^{1.585}), by reducing four half-size multiplications to three. It is the standard example of divide-and-conquer beating the obvious bound, and 4.12 derives it.
• Fast Fourier Transform based methods — O(n \log n), used by real big-integer libraries for very large numbers.

Python switches to Karatsuba above a few thousand digits. At 200 digits the schoolbook method wins on constants, which is why this is the right algorithm here.

Where this goes next

• Add Strings, Add Binary — the same carry discipline in one dimension.
• Plus One — the simplest case. 4.28.5.
• Big-integer libraries — every one of them is this loop, in a base like 2^{32} rather than 10, because a larger base means fewer digits and fewer carries.

What the interviewer will push on

"Derive the index formula." Place values multiply, so the exponents add — and check it on "12" × "34".

"How long can the result be?" m + n at most, m + n − 1 at least, hence a single leading zero to strip.

"Why += and not =?" Several pairs land on the same position, and carries accumulate.

"Why does the carry not need normalising immediately?" The right-to-left order means that position is visited later, and it normalises then.

"Can you do better than O(mn)?" Karatsuba, then FFT. Say why they do not help at 200 digits.

One thing to volunteer: verify the index formula on a two-by-two example out loud before writing the loops. It is the only part of this problem that can be wrong, and checking it costs ten seconds.

Next: 4.28.8 Detect Squares — geometry with a counting map, and the last problem in this group.