Multiply Strings

MEDIUM✓ CHIP-TIMEDLC #43 — FULL STATEMENT ↗

The drill: Multiply two non-negative integers given as digit strings and hand back their product, also as a string — the numbers may be too long for a built-in integer type to hold along the way.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two non-negative integers arrive as strings of digits, potentially far too long to fit into any built-in integer type, and the task is to multiply them together.

The product has to be computed using only string and digit-level arithmetic — no shortcut through a native numeric type that could silently overflow or lose precision on inputs this large.

The result comes back as a string too, holding the exact product with no leading zeros, unless the true product is zero itself, in which case a single "0" is the right answer.

EX 01

num1 = "2" · num2 = "3"

→ "6"

SINGLE DIGITS, NO CARRY

EX 02

num1 = "0" · num2 = "0"

→ "0"

ZERO TIMES ZERO

EX 03

num1 = "0" · num2 = "582"

→ "0"

ZERO SHORT-CIRCUITS REGARDLESS OF THE OTHER OPERAND

each digit string runs up to a couple hundred characters
both inputs are non-negative integers with no leading zeros, other than "0" itself
the product must be built without casting either input to a native integer
the returned string carries no leading zeros except for a lone "0"

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Casting straight to a native integer dodges the actual exercise — for numbers that could run hundreds of digits long, the arithmetic has to live entirely on the strings. How did you multiply big numbers on paper, before a calculator?

HINT 2 THE STRUCTURE

Every digit of the first number times every digit of the second contributes to exactly one place value. The digit at position i from the right in num1 and position j from the right in num2 always lands at position i+j (and possibly carries into i+j+1) — no matter what the rest of the numbers look like.

HINT 3 ONE STEP FROM THE ANSWER

Multiply into a result array sized len(num1)+len(num2): for each digit pair, add the product into position i+j and let the carry spill into i+j+1. One final pass resolves leftover carries and trims a possible leading zero.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE DIGIT CONVOLUTIONPATTERN · DIGIT CONVOLUTIONnum1 = "12" · num2 = "34"

STEP 1

12 × 34: allocate a result array sized len(num1)+len(num2) = 4, all zero. Every digit pair has one fixed destination.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/multiply-strings.py — RACE PACE

LANG ▸

PACE ▸

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

        n, m = len(num1), len(num2)
        result = [0] * (n + m)  # result[i+j] and result[i+j+1] absorb every digit pair

        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                p1, p2 = i + j, i + j + 1
                total = mul + result[p2]
                result[p2] = total % 10
                result[p1] += total // 10

        start = 0
        while start < len(result) - 1 and result[start] == 0:
            start += 1
        return "".join(map(str, result[start:]))

TIME O(N·M)SPACE O(N+M)PYTHON · RACE PACE · 20 LN

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 = len(a) - 1, len(b) - 1, 0
            out = []
            while i >= 0 or j >= 0 or carry:
                d1 = int(a[i]) if i >= 0 else 0
                d2 = int(b[j]) if j >= 0 else 0
                total = d1 + d2 + carry
                out.append(str(total % 10))
                carry = total // 10
                i -= 1
                j -= 1
            return "".join(reversed(out))

        total = "0"
        shift = 0
        for j in range(len(num2) - 1, -1, -1):        # one digit of num2 at a time
            digit = int(num2[j])
            carry = 0
            partial = []
            for i in range(len(num1) - 1, -1, -1):     # multiply the whole of num1 by it
                prod = int(num1[i]) * digit + carry
                partial.append(str(prod % 10))
                carry = prod // 10
            if carry:
                partial.append(str(carry))
            partial_str = "".join(reversed(partial)) + "0" * shift  # shift into place
            total = add(total, partial_str)            # fold into the running total
            shift += 1
        return total

TIME O(N·M)SPACE O(N+M)PYTHON · TRAINING PACE · 34 LN

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int n = num1.length(), m = num2.length();
        int[] result = new int[n + m]; // result[i+j] and result[i+j+1] absorb every digit pair

        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;
                int total = mul + result[p2];
                result[p2] = total % 10;
                result[p1] += total / 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        int start = 0;
        while (start < result.length - 1 && result[start] == 0) {
            start++;
        }
        for (int k = start; k < result.length; k++) {
            sb.append(result[k]);
        }
        return sb.toString();
    }
}

TIME O(N·M)SPACE O(N+M)JAVA · RACE PACE · 30 LN

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        String total = "0";
        int shift = 0;
        for (int j = num2.length() - 1; j >= 0; j--) {     // one digit of num2 at a time
            int digit = num2.charAt(j) - '0';
            StringBuilder partial = new StringBuilder();
            int carry = 0;
            for (int i = num1.length() - 1; i >= 0; i--) { // multiply the whole of num1 by it
                int prod = (num1.charAt(i) - '0') * digit + carry;
                partial.append(prod % 10);
                carry = prod / 10;
            }
            if (carry > 0) {
                partial.append(carry);
            }
            partial.reverse();
            for (int k = 0; k < shift; k++) {
                partial.append('0');                        // shift into place
            }
            total = add(total, partial.toString());          // fold into the running total
            shift++;
        }
        return total;
    }

    private String add(String a, String b) {
        StringBuilder out = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            int d1 = i >= 0 ? a.charAt(i) - '0' : 0;
            int d2 = j >= 0 ? b.charAt(j) - '0' : 0;
            int total = d1 + d2 + carry;
            out.append(total % 10);
            carry = total / 10;
            i--;
            j--;
        }
        return out.reverse().toString();
    }
}

TIME O(N·M)SPACE O(N+M)JAVA · TRAINING PACE · 45 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED