LeetCode 43 · Math & Geometry

Multiply Strings, explained with a picture

Long multiplication on squared paper.

MediumMath & Geometry
▶ Watch it step by step

The problem

Multiply two non-negative numbers given as strings, without converting them directly to integers. Return the product as a string.

Input:  "123" × "45"
Output: "5535"

Picture it

Picture long multiplication on squared paper, the way it’s taught at school. Each digit of one number is multiplied by each digit of the other, and the result lands in a specific column: digit i times digit j always goes into column i + j + 1, with the tens carried one column left.

How to recognise it

  • Numbers are given as strings and may be far too long for a normal integer (up to 200 digits here).
  • You are told not to convert them directly to integers.
  • The method is the one from school: multiply digit by digit and add up the carries.
  • Every digit pair lands in a predictable column, so an array indexed by position can hold the result.
  • The answer is again a string, with no leading zeros.

Start with brute force

Multiplication is repeated addition. Add the first number to a running total as many times as the second number says, using string addition.

def multiply_brute(a, b):
    total = "0"
    for _ in range(int(b)):          # already converts b, which the problem forbids
        total = add_strings(total, a)
    return total

Here add_strings adds two digit strings from the right with a carry. The loop runs b times, so for a 200-digit b that is up to 10^200 additions, which can never finish. Even for small b it breaks the rule by calling int(b). Space is O(n).

From brute force to the idea

  1. Do school long multiplication. Each digit of a times each digit of b is a small product of at most 81.
  2. Find the column. Counting from the left, digit i of a and digit j of b contribute to column i + j + 1 (the ones part) and column i + j (the carry). The result of an n-digit and m-digit multiplication has n + m digits at most, so the array res has len(a) + len(b) slots.
  3. Go from the right. The loops run from the last digit backwards, so smaller place values are finished first.
  4. Add to what is already there. p = int(a[i]) * int(b[j]) + res[i + j + 1] includes the digit already stored in that column. Then res[i + j + 1] = p % 10 keeps the ones digit, and res[i + j] += p // 10 pushes the carry one column left.
  5. Tidy up. The array becomes a string, leading zeros are removed with lstrip("0"), and or "0" keeps a single zero when the product is 0.

This is the key idea: every digit product has a fixed home column, and carries move one column left.

The key idea

An array of n + m slots; add every digit product into slot i + j + 1 and carry. O(n × m).

Python solution

def multiply(a, b):
    res = [0] * (len(a) + len(b))
    for i in range(len(a) - 1, -1, -1):
        for j in range(len(b) - 1, -1, -1):
            p = int(a[i]) * int(b[j]) + res[i + j + 1]
            res[i + j + 1] = p % 10          # keep the ones digit
            res[i + j] += p // 10            # carry to the left
    s = "".join(map(str, res)).lstrip("0")
    return s or "0"

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (repeated addition)O(b · n): b additions of an n-digit number, b up to 10^200O(n)
Digit by digit (shown code)O(n · m): one small multiplication per pair of digits, about 40,000 for two 200-digit numbersO(n + m): the result array

Edge cases

  • Either factor is "0": returns "0". Without the final or "0" it would return an empty string.
  • The product has one fewer digit than n + m ("123" × "45"): the array is [0, 5, 5, 3, 5], and the leading zero is stripped to give "5535".
  • All nines ("999" × "999"): returns "998001", and 200 nines times 200 nines matches Python's own integer result.
  • Trailing zeros ("10" × "10"): returns "100".
  • Temporary values above 9: a slot can briefly hold more than 9 (for 99 × 99 it reaches 17), but it is reduced to a digit before the end, because every slot is later used as a "ones" slot. After the loops all slots are single digits.
  • Leading zeros in the input ("007" × "3"): still fine, and gives "21". The problem promises none.

Common mistakes

  • Forgetting to strip the leading zero, so "123" × "45" becomes "05535".
  • Dropping or "0" so a zero product returns an empty string.
  • Not adding the old value res[i + j + 1], so carries from earlier pairs are lost ("99" × "99" gives "8111").
  • Using columns i + j and i + j - 1 instead of i + j + 1 and i + j, which shifts the answer ("123" × "45" gives "55350").
Your turn: add two number strings

Add two non-negative numbers given as strings, again without converting them to integers. For "456" and "77" the answer is "533". Describe your approach, then write it if you like.

Compare with our answer

Use the same school method: start at the right ends, add digit by digit with a carry, and keep going while either string or the carry has something left.

def add_strings(a, b):
    i, j, carry = len(a) - 1, len(b) - 1, 0
    out = []
    while i >= 0 or j >= 0 or carry:
        total = carry
        if i >= 0:
            total += int(a[i]); i -= 1
        if j >= 0:
            total += int(b[j]); j -= 1
        out.append(str(total % 10))
        carry = total // 10
    return "".join(reversed(out))

add_strings("999", "1") is "1000", add_strings("0", "0") is "0", and it agrees with Python's integers on a thousand random pairs. Time O(max(n, m)), space O(max(n, m)).

A strong answer mentions: working from the right, continuing while a carry is left, and reversing the digits at the end.

Check what stuck

1. You must add up two numbers with 500 digits each, given as strings, without using big-integer conversion. Which approach fits best?

2. In the shown code, where does the carry of the digit product a[i] × b[j] go?

3. A learner removes or "0" from the last line. What does multiply("0", "999") return?

Score 60% or more and the lesson is marked complete.