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.

Restating the Problem: You are given two numbers represented as strings. You must multiply them and return the result as a string. The catch is that you cannot just convert them to int and multiply them directly, because in the real world (or languages without arbitrary precision), these numbers would overflow standard data types.

• Constraints to note: Both strings consist only of digits and can be up to 200 characters long.
• Edge cases: Multiplying by "0" should yield exactly "0", avoiding "000".

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

Up to 200 digits each.

Brute Force Approach

The "brute force" here isn't an algorithm, but rather the cheating approach: return str(int(num1) * int(num2)). This works natively in Python because Python automatically handles arbitrarily large integers. However, this violates the spirit of the question. The intended naive approach is simulating repeated addition (adding num1 to itself num2 times), but that would take O(10^{\text{len}(num2)}) operations, which is astronomically slow. We must simulate long multiplication.

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.

Code Walkthrough:

• Zero Check: If either string is "0", we immediately return "0".
• Initialization: We create an array result of size m + n filled with zeros, as this is the maximum possible length of the product.
• Nested Loops: We loop through num1 (index i) and num2 (index j) from right to left (least significant digits first).
• Multiplication: We compute the product of the two digits num1[i] and num2[j].
• Accumulation: We add this product to whatever value is already sitting at the target position result[i + j + 1].
• Carry: We place the single digit into result[i + j + 1] using modulo 10 (total % 10), and we carry the tens place over to the next left position result[i + j] using integer division (total // 10).
• Formatting: Finally, we find the starting position (ignoring a possible leading zero at result[0]) and join the array into a string.

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.

• Time Complexity: O(mn). We have two nested loops, one iterating m times and the other n times. Each inner step does O(1) arithmetic operations.
• Space Complexity: O(m + n). We allocate a result array of size m + n to store the intermediate digits.

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.