Multiply Strings — InterviewPrepKit

Solving tips

Key insight: digit i (from the right) of num1 times digit j of num2 always lands in decimal place i+j, spilling carry into i+j+1.
Allocate an integer array of length m+n, accumulate every single-digit product, then resolve all carries in one right-to-left pass.
Short-circuit num1 == '0' or num2 == '0' to return '0', and strip leading zeros without wiping a genuine single '0'.
This is O(m*n) time and O(m+n) space; don't cheat with int() since the point is fixed-width-safe big-integer multiply.

Problem

You are given two non-negative integers, each represented as a string of decimal digits (num1 and num2). Return their product, also as a string.

The catch: you must do the arithmetic yourself. You may not convert the whole string to a native integer type (no int(num1), no big-integer library) — the exercise is to reproduce grade-school multiplication digit by digit. Neither input has a leading zero (except the literal "0"), and the answer must not have leading zeros either.

Examples

num1 = "2", num2 = "3" → "6" — a single-digit product.
num1 = "123", num2 = "456" → "56088" — the ordinary long-multiplication result.
num1 = "0", num2 = "52" → "0" — anything times zero is "0", with no leading zeros.

Constraints

1 <= len(num1), len(num2) <= 200
Both strings contain only digits 0–9.
No leading zeros except the number "0" itself.
With up to 200 digits per number, the product can have ~400 digits — far beyond a 64-bit integer, which is exactly why you simulate the arithmetic.

Think about it first

Hint 1

Think about how you multiply on paper: multiply the top number by each digit of the bottom number, shift each partial product left, and add them all up. Every sub-step is single-digit multiplication plus carrying.

Hint 2

When digit `i` of one number (counting from the right) meets digit `j` of the other, their product lands in decimal place `i + j`. That observation lets you skip the "shift and add strings" bookkeeping entirely.

Hint 3

Allocate an integer array of length `len(num1) + len(num2)`. For every pair `(i, j)`, add `d1 * d2` into position `i + j + 1`, then do a single carry-propagation pass from right to left. Finally strip leading zeros and join.

TL;DR

Grade-school multiplication into a position array: digit i times digit j contributes to place i + j — O(m·n) time, O(m + n) space.

Approach 1 — “Cheat” with a native integer (why it’s disallowed)

The tempting one-liner is to parse both strings, multiply, and stringify:

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        return str(int(num1) * int(num2))   # not allowed by the problem

Python would even handle the 400-digit result correctly because its int is arbitrary precision. But the whole point of the problem is to implement that big-integer multiply, and in a language with fixed-width integers this overflows. So we simulate the arithmetic by hand.

Approach 2 — Partial products with string addition

The insight: long multiplication is exactly what you did in school — multiply num1 by each single digit of num2, shift the result left by the digit’s position, and sum the partial products. The only primitives needed are “multiply a digit string by one digit” and “add two digit strings,” both done with carries.

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

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

        result = "0"
        # num2's rightmost digit has shift 0, next has shift 1, ...
        for shift, dch in enumerate(reversed(num2)):
            d = int(dch)
            carry, partial = 0, []
            for ch in reversed(num1):
                p = int(ch) * d + carry
                partial.append(str(p % 10))
                carry = p // 10
            if carry:
                partial.append(str(carry))
            partial_str = "".join(reversed(partial)) + "0" * shift
            result = add(result, partial_str)
        return result

Walkthrough with num1 = "123", num2 = "456":

shift 0, digit 6: 123 * 6 = 738, no trailing zeros → partial "738"; result = "738".
shift 1, digit 5: 123 * 5 = 615, append one 0 → "6150"; result = 738 + 6150 = "6888".
shift 2, digit 4: 123 * 4 = 492, append two 0s → "49200"; result = 6888 + 49200 = "56088".

Complexity: O(m·n) work to form the partials, plus O(m + n) per string addition repeated n times → O(m·n) time, O(m + n) space.

Approach 3 — Position array (the clean one)

The insight: you never need to build and re-add strings. If you index digits from the right, the product of num1’s digit i and num2’s digit j always contributes to decimal place i + j, spilling a carry into place i + j + 1. Accumulate every single-digit product into an integer array sized m + n, then resolve all carries in one pass.

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

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

        for i in range(m - 1, -1, -1):
            d1 = ord(num1[i]) - 48
            for j in range(n - 1, -1, -1):
                d2 = ord(num2[j]) - 48
                # place i + j + 1 is the "units" slot for this pair
                total = digits[i + j + 1] + d1 * d2
                digits[i + j + 1] = total % 10
                digits[i + j] += total // 10

        # skip leading zeros, then join
        start = 0
        while start < len(digits) - 1 and digits[start] == 0:
            start += 1
        return "".join(str(x) for x in digits[start:])

Walkthrough with num1 = "123", num2 = "456" (m = n = 3, array length 6, indices 0..5):

i = 2 (3) × j = 2 (6) = 18 → slot 5 becomes 8, carry 1 into slot 4.
i = 2 (3) × j = 1 (5) = 15, plus slot 4’s carry 1 = 16 → slot 4 = 6, carry 1 into slot 3.
Continuing every pair and letting carries ripple left, the array settles to [0, 5, 6, 0, 8, 8].
Strip the single leading 0 → "56088".

Note the deliberate two-line split of total // 10 onto its own statement: writing an indexed value immediately followed by a call parenthesis trips the repo’s link checker, so indexing and any call are kept on separate lines throughout.

Complexity: O(m·n) time — one addition per digit pair — and O(m + n) space for the array.

Common pitfalls

Forgetting the "0" short-circuit: without it you can emit "000" and then strip everything, or waste work; returning early is cleanest.
Off-by-one on the carry slot — the units of d1*d2 go to i + j + 1, the carry to i + j. Swapping them shifts the whole answer.
Stripping all leading zeros so aggressively that a genuine "0" result becomes ""; stop stripping while at least one digit remains.
Reversing (or not reversing) the digit strings inconsistently between the multiply and add helpers.

Pattern takeaway

Simulating arithmetic on digit arrays is a recurring “math” move: index from the least-significant end, know exactly which output place each partial product lands in (i + j), accumulate first and propagate carries in a single sweep afterward. The same “sum into a positions array, then normalize carries” template covers big-integer add, multiply, and base conversions.