Multiply Strings

Multiply Strings asks you to multiply two non-negative integers given as strings, without converting them to a built-in big integer. The trick is to reproduce the grade-school multiplication you already know, but write each partial product straight into a fixed-size digit buffer.

The slow way first

The tempting shortcut is str(int(num1) * int(num2)), but the problem forbids converting the whole string to an integer. The honest approach is long multiplication: multiply num1 by each digit of num2, shift each partial product, and add them all up. Done naively with string addition, the bookkeeping (alignment, carries across separate rows) is fiddly and error-prone.

The question to ask: where exactly does each single-digit product belong in the final answer? If we can place every digit × digit product directly, we never have to add whole rows together.

The idea: one shared digit buffer

An m-digit number times an n-digit number has at most m + n digits. So allocate a result buffer res of length m + n, all zeros. For digit i of num1 and digit j of num2, the product d1 * d2 belongs at position res[i + j + 1], with any carry flowing into res[i + j]. Add the product in, split off the carry, and move on. Every partial product accumulates into the same buffer.

The key insight: the positions i + j and i + j + 1 come straight from how place value works. Units times units stays near the end of the buffer; the leading digits feed the front.

Walk through it

Step through the animation. The two operands sit on top; the length-4 buffer sits below. Pointers i and j mark the digits being multiplied. We start from the last digit of each number. 2 × 4 = 8 lands in res[3]; 2 × 2 = 4 and 1 × 4 = 4 both feed res[2] (so it grows to 8); 1 × 2 = 2 feeds res[1]. None of these single-digit sums overflow, so every carry is 0. The buffer ends as [0, 2, 8, 8], and dropping the leading zero gives "288".

Pseudocode

m, n = lengths of num1, num2
res = array of (m + n) zeros
for i from m-1 down to 0:
    for j from n-1 down to 0:
        product = digit(num1, i) * digit(num2, j)
        res[i + j + 1] += product
        carry = res[i + j + 1] // 10        # tens place
        res[i + j] += carry                 # push carry left
        res[i + j + 1] %= 10                # keep only the ones place
join res into a string, drop leading zeros
return that string (or "0" if it is empty)

The Python solution

def multiply(num1, num2):
    m, n = len(num1), len(num2)
    res = [0] * (m + n)
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            d1 = int(num1[i])
            d2 = int(num2[j])
            res[i + j + 1] += d1 * d2
            carry = res[i + j + 1] // 10
            res[i + j] += carry
            res[i + j + 1] %= 10
    digits = ''.join(map(str, res)).lstrip('0')
    return digits or '0'

• res is the shared buffer of length m + n, holding one decimal digit per slot once carries settle.
• The two loops run right to left over both numbers, just like multiplying by hand.
• res[i + j + 1] += d1 * d2 drops the raw product into its place — it may briefly exceed 9.
• Lines 9 to 11 are the carry: // 10 is the tens place pushed left into res[i + j], and %= 10 keeps only the ones place in the current slot.
• At the end we stringify, strip leading zeros, and fall back to '0' so an all-zero result is not the empty string.

Complexity

We do constant work per digit pair, so the running time is O(m·n) and the extra space is the buffer of size O(m + n). There is no faster comparison-free way to multiply two arbitrary numbers digit by digit.

When this pattern shows up

Practice