Multiply Strings

The problem

num1 and num2 are whole numbers, zero or more, written as strings of decimal digits. Neither has extra zeros in front, so only the number 0 starts with a 0. Return their product as a string written the same way. You may not turn a whole input string into a number, whatever your language offers for that (Number, BigInt, int). Turning one character at a time into a digit is allowed.

What to write

function solve(num1: string, num2: string): string

Input
num1 = "2"
num2 = "3"

Output
"6"

Input
num1 = "123"
num2 = "456"

Output
"56088"

Constraints

Inputs have no leading zeros except the single digit zero and at most 200 digits.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Each string can hold 200 digits, and the task forbids turning a whole string into a number. In JavaScript it would not fit anyway: a number is exact only up to 9,007,199,254,740,991, which has 16 digits. Single digits are small, though: multiplying two of them never gives more than 81.

2. Hint 2: Ask a smaller question

   Multiply 23 by 4 on paper, and then 23 by 40. In which column does the result of 3 × 4 end up each time? What decides the column where the product of two digits belongs?

3. Hint 3: Name the pattern

   This is the long multiplication from school: multiply every digit of one number by every digit of the other, put each small product in the column its two digits decide, and carry what does not fit to the left. Working through numbers one digit at a time is digit-by-digit arithmetic. The signal: numbers too long to convert. Read the lesson on digit-by-digit arithmetic.

4. Hint 4: State the invariant

   Give the answer one slot per input digit. The digits at positions i and j, counted from 0 on the left, meet in slot i + j + 1, and their carry goes to slot i + j. After every pair, the slots read as one number: the sum of the small products so far, each at its own place.

5. Hint 5: Sketch the pseudocode

   Make one slot of 0 per input character. For every pair of positions, i in num1 and j in num2, each going from last to first: total = digit i × digit j + slot i + j + 1. That slot keeps total's last digit; slot i + j gains the rest. Drop leading zeros, keeping one digit. Join.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Use grade-school multiplication: each digit pair contributes to two adjacent positions, with carries accumulated toward the left.

The slow way

Turn both strings into numbers, multiply, and turn the product back into a string. The task forbids that. In JavaScript it can also be wrong once the product passes 9,007,199,254,740,991: 123456789 × 987654321 comes out as 121932631112635260, not 121932631112635269. Python's whole numbers have no size limit, but the rule applies there too.

The insight

Long multiplication is made of small ones: each digit of one number times each digit of the other. Where a small product belongs depends only on how far its two digits are from the right end: those distances add up. So every small product can go straight into its slot of the answer, with a carry for what does not fit.

Step by step

1. Make one slot for every digit the product can have, all 0. A number of m digits times a number of n digits has at most m + n digits: 999 × 999 = 998001 has six. Every slot starts at 0 so that small products can be added into it.
2. Pair every digit of num1 with every digit of num2, last digits first. A carry moves one slot to the left. Working from the right, a later pair still handles that slot and takes the carry in. Only the very last carry has no later pair: it lands in the first slot.
3. Multiply the two digits and add what their slot already holds. Digits at positions i and j from the left belong in slot i + j + 1, because their distances from the right end add up. The slot may hold earlier products or a carry already, so add them in.
4. The slot keeps the last digit of that total. A slot is one place of the answer, and one place holds one digit. The last digit of the total is the part that belongs to this place.
5. The rest of the total is carried to the slot on the left. One place to the left is worth ten times more, so each full ten in the total counts as 1 there. The carry is added, not written over, because the left slot may already hold something.
6. Remove zeros from the front, but never the only digit. The slots were sized for the longest possible product. A shorter one leaves a 0 in front: 2 × 3 fills its two slots as 0 and 6. A product of 0 is all zeros and must keep one.
7. Join the slots into one string. Each slot now holds one digit of the product, leftmost digit first. The answer has to be a string, written the same way as the inputs.

The same numbered steps are the comments in each solution.

function solve(num1, num2) {
    // 1. Make one slot for every digit the product can have, all 0
    const out = Array(num1.length + num2.length).fill(0);
    // 2. Pair every digit of num1 with every digit of num2, last digits first
    for (let i = num1.length - 1; i >= 0; i--)
        for (let j = num2.length - 1; j >= 0; j--) {
            // 3. Multiply the two digits and add what their slot already holds
            const sum = Number(num1[i]) * Number(num2[j]) + out[i + j + 1];
            // 4. The slot keeps the last digit of that total
            out[i + j + 1] = sum % 10;
            // 5. The rest of the total is carried to the slot on the left
            out[i + j] += Math.floor(sum / 10);
        }
    // 6. Remove zeros from the front, but never the only digit
    while (out.length > 1 && out[0] === 0)
        out.shift();
    // 7. Join the slots into one string
    return out.join("");
}

function solve(num1: string, num2: string): string {
  // 1. Make one slot for every digit the product can have, all 0
  const out = Array(num1.length + num2.length).fill(0);
  // 2. Pair every digit of num1 with every digit of num2, last digits first
  for (let i = num1.length - 1; i >= 0; i--)
    for (let j = num2.length - 1; j >= 0; j--) {
      // 3. Multiply the two digits and add what their slot already holds
      const sum = Number(num1[i]) * Number(num2[j]) + out[i + j + 1];
      // 4. The slot keeps the last digit of that total
      out[i + j + 1] = sum % 10;
      // 5. The rest of the total is carried to the slot on the left
      out[i + j] += Math.floor(sum / 10);
    }
  // 6. Remove zeros from the front, but never the only digit
  while (out.length > 1 && out[0] === 0) out.shift();
  // 7. Join the slots into one string
  return out.join("");
}

def solve(num1, num2):
    # 1. Make one slot for every digit the product can have, all 0
    out = [0] * (len(num1) + len(num2))
    # 2. Pair every digit of num1 with every digit of num2, last digits first
    for i in reversed(range(len(num1))):
        for j in reversed(range(len(num2))):
            # 3. Multiply the two digits and add what their slot already holds
            total = int(num1[i]) * int(num2[j]) + out[i + j + 1]
            # 4. The slot keeps the last digit of that total
            out[i + j + 1] = total % 10
            # 5. The rest of the total is carried to the slot on the left
            out[i + j] += total // 10
    # 6. Remove zeros from the front, but never the only digit
    while len(out) > 1 and out[0] == 0:
        out.pop(0)
    # 7. Join the slots into one string
    return "".join(map(str, out))

Example 2, traced

Input
num1 = "123"
num2 = "456"

Output
"56088"

Why it works

After every pair, the slots read as one number: the sum of the small products handled so far, each at its own place. Splitting a total into a kept digit and a carry does not change that number, because 1 in the left slot is worth 10 in this one. A slot may pass 9 for a moment, 17 during 99 × 99, until a later pair handles it.

Time and space

Time O(m n), extra space O(m + n). Each of the m digits of num1 meets each of the n digits of num2 once: m × n pairs, so the multiplying takes O(m n) time. Only a factor of 0 costs more: each zero removed moves every slot behind it. The slots are the O(m + n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Both writes add to what a slot holds: the slot's value joins the total, and the carry is added to the left slot. Skip the first and 123 × 456 gives 45628; assign the carry and the result is 45788.
• The digit goes to slot i + j + 1 and the carry to slot i + j. One slot further left for both, and 2 × 3 comes out as 60, ten times too much.
• Remove the zeros in front, but stop at the last digit. Without the removal, 2 × 3 comes out as 06. Without the stop, 0 × 999 loses every digit: an empty string in JavaScript, an error in Python.

Pattern

Digit-by-digit arithmetic. Builds on Add Two Numbers and Plus One.

Keep going