Multiply Strings

Problem in Plain English

Multiply two non-negative integers supplied as decimal strings and return the product as a string, without converting either input to an integer or using a big-integer library.

Problem Statement

Given two non-negative integers num1 and num2 represented as decimal strings, return their product, also represented as a decimal string.

The inputs can hold up to 200 digits, far beyond what a fixed-width integer stores, so the digits must be combined by hand. Do not convert the whole strings to integers and do not use a big-integer library.

Constraints

$1 \leq \text{num1.length}, \text{num2.length} \leq 200$ .
num1 and num2 consist of digits only.
Neither input has a leading zero, except the number 0 itself.

Examples

Example 1

Input: num1 = "2", num2 = "3"
Output: "6"

The only digit pair contributes $2 \times 3 = 6$ units, so the canonical decimal result is "6".

Example 2

Input: num1 = "123", num2 = "456"
Output: "56088"

The shifted rows are 738, 6150 and 49200, whose sum is 56088. Several columns receive contributions, so their carries must be preserved.

Example 3

Input: num1 = "0", num2 = "999"
Output: "0"

Zero times any non-negative integer is zero. Return exactly "0", without extra leading zeros or an empty string.

Example 4

Input: num1 = "99", num2 = "99"
Output: "9801"

The units row is 891 and the tens row is 8910. Their sum 9801 shows that a carry can propagate across overlapping partial products.

Intuition

Decimal place value lets us multiply arbitrarily long inputs using only small digit arithmetic. In Example 1, the units digits 2 and 3 contribute 6 units. For a longer input, every digit pair contributes at its combined place value; add those contributions and carry each group of ten into the next column. Whole-number conversion is unnecessary.

Approaches

Partial Products

Solution Details

Reveal Partial Products: intuition, complexity, and code

Intuition

Paper multiplication builds one partial product per digit of num2 and then adds them all up. Each partial product is just num1 times a single digit, shifted by its place, so the whole job reduces to single-digit multiplication plus string addition.

Step-by-Step Logic

Return "0" if either input is zero; otherwise initialize total to "0". Example 1 has two nonzero inputs, so continue.
Visit num2 from right to left. Multiply every digit of num1 by the current digit, processing from units toward higher places with a carry. In Example 1, the single product is 6, so append digit 6 and carry 0.
Reverse the collected digits, then append one zero for each position to the right of the current num2 digit. Example 1 has shift 0 and row "6".
Add the shifted row into total from right to left, carrying sums of ten or more. Here zero plus six gives digit 6 and carry 0.
Repeat for all num2 digits and return total. Example 1 has one row and returns "6".

Why It Works

Multiplying a digit from right to left writes the remainder modulo ten and passes the quotient to the next column, preserving the exact value of the partial product. Appending one zero per position multiplies that row by the corresponding power of ten. String addition uses the same remainder/carry identity. After each row, total equals the sum of all processed digit contributions; decimal distributivity says the sum of every row is exactly the full product. A nonzero most-significant row produces a canonical final result; the early zero return handles zero inputs.

Dry Run

Partial Products: variable states at each step
Stage	i / j	Digit calculation	Carry before → after	Row / total
initialize	i = 0	digit = 3, shift = 0	0	total = "0"
multiply row	j = 0	2 × 3 + 0 = 6	0 → 0	reverse digits = [6]
finish row	j = -1	no final carry, reverse and shift	0	row = "6"
add row	a index 0, b index 0	0 + 6 + 0 = 6	0 → 0	reverse sum digits = [6]
finish / return	both indices -1	no further row	0	total = "6"

Complexity Analysis

Time Complexity

O(n(m + n))

Space Complexity

O(m + n)

Let m and n be the lengths of num1 and num2. There are n rows. Building a row scans m digits and appends up to n shift zeros; adding it scans at most m + n digits. Thus worst-case work is O(n(m + n)), including zero rows and repeated string creation. Each iteration allocates row buffers and a new total, but only O(m + n) characters are live at once, including the returned string. Cumulative allocation is O(n(m + n)); zero-input early return costs O(1).

Code

Solution.java

1class Solution {2    public String multiply(String num1, String num2) {3        if (num1.equals("0") || num2.equals("0")) {4            return "0";5        }6        String total = "0";7        int n = num2.length();8        for (int i = n - 1; i >= 0; i--) {9            int digit = num2.charAt(i) - '0';10            StringBuilder shifted = new StringBuilder(multiplyByDigit(num1, digit));11            for (int k = 0; k < n - 1 - i; k++) {12                shifted.append('0');13            }14            // The shift aligns this row with the digit's decimal place.15            total = addStrings(total, shifted.toString());16        }17        return total;18    }19
20    private String multiplyByDigit(String num, int digit) {21        if (digit == 0) {22            return "0";23        }24        StringBuilder sb = new StringBuilder();25        int carry = 0;26        for (int j = num.length() - 1; j >= 0; j--) {27            // Emit one units digit; carry preserves the higher-place contribution.28            int prod = (num.charAt(j) - '0') * digit + carry;29            sb.append((char) ('0' + (prod % 10)));30            carry = prod / 10;31        }32        while (carry > 0) {33            sb.append((char) ('0' + (carry % 10)));34            carry /= 10;35        }36        return sb.reverse().toString();37    }38
39    private String addStrings(String a, String b) {40        StringBuilder sb = new StringBuilder();41        int i = a.length() - 1;42        int j = b.length() - 1;43        int carry = 0;44        while (i >= 0 || j >= 0 || carry > 0) {45            int sum = carry;46            if (i >= 0) {47                sum += a.charAt(i--) - '0';48            }49            if (j >= 0) {50                sum += b.charAt(j--) - '0';51            }52            sb.append((char) ('0' + (sum % 10)));53            carry = sum / 10;54        }55        return sb.reverse().toString();56    }57}

Hints

Hint 1

Do the multiplication on paper for 123 times 456: each digit of 456 produces its own shifted row before anything is added.

Hint 2

A digit at index i of num1 times a digit at index j of num2 always lands on the same answer positions: i + j and i + j + 1.

Hint 3

Use an array of m + n answer slots. For each pair, combine the existing units slot with the product, store its remainder modulo ten, and add its quotient to the slot immediately left.

Edge Cases

Either input is "0": return "0" at once instead of building an empty result.
Maximum-length inputs of 200 digits: the pairwise loops still run fast, but converting to a number would overflow.
Leading zeros in the result array, such as the spare slot when the product is short — strip them before joining.
Internal zero digits such as "101" times "20" still need their correct decimal shifts; the result is "2020".
Long runs of nines cause overlapping carries: "99" times "99" yields "9801", not separate concatenated digit products.

Common Mistakes and Interview Tips

Converting both strings to integers first, which overflows on long inputs and breaks the no-conversion rule.
Writing the carry into res[i + j] with plain assignment instead of +=, wiping out carries left by earlier pairs.
Forgetting to skip leading zeros, so short products come out with extra 0 digits at the front.
Processing the array in an arbitrary order can leave unnormalized carry slots; the shown code relies on both loops moving right to left.
Interview tip: derive slot i + j + 1 from decimal weights before coding; explain why the left carry uses addition and can temporarily exceed nine.

Key Takeaway

Represent long decimal arithmetic by small digit contributions and their place values. Either add shifted rows or accumulate in a shared array; carry operations must preserve the represented value at every step.