Multiply Strings

Examples

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

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

123 * 456 = 56088, computed digit by digit without ever converting the full strings to numbers.

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

Constraints

• 1 <= num1.length, num2.length <= 200

• num1 and num2 consist of digits only.

• Neither num1 nor num2 has leading zeros, except num1 and num2 themselves being exactly "0".

Approach

This is the grade-school multiplication algorithm, just done on digit strings instead of numbers you already know how to multiply directly. One way to do it: multiply the first number by a single digit of the second number at a time, right to left, padding each of those partial products with the right number of trailing zeros for its place value, and add every partial product into a running total using ordinary string addition. It's correct, but each of those additions redoes work across digits that were already settled by earlier additions.

A more direct approach skips the repeated string additions entirely. Multiplying digit num1[i] by digit num2[j] always contributes to exactly two positions of the final answer (its own digit, plus a possible carry into the position to its left) - based only on i + j. Accumulating every digit-pair's contribution straight into a results array, indexed by position, produces the entire answer in a single pass, with only one conversion back to a string at the very end.

Solutions

Brute Force - Digit-by-Digit With String Addition

For each digit of num2 (right to left), multiply it against the entire num1 to get a partial product, pad it with trailing zeros for its place value, and add it into a running total using ordinary string addition.

function multiply(num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";

  let result = "0";

  for (let i = num2.length - 1; i >= 0; i--) {
    const digit = Number(num2[i]);
    let carry = 0;
    let partial = "";

    for (let j = num1.length - 1; j >= 0; j--) {
      const product = Number(num1[j]) * digit + carry;
      partial = (product % 10) + partial;
      carry = Math.floor(product / 10);
    }
    if (carry > 0) partial = carry + partial;

    // Shift this partial product left by its place value
    partial += "0".repeat(num2.length - 1 - i);

    result = addStrings(result, partial);
  }

  return result;
}

function addStrings(a, b) {
  let result = "";
  let carry = 0;
  let i = a.length - 1;
  let j = b.length - 1;

  while (i >= 0 || j >= 0 || carry > 0) {
    const digitA = i >= 0 ? Number(a[i]) : 0;
    const digitB = j >= 0 ? Number(b[j]) : 0;
    const sum = digitA + digitB + carry;
    result = (sum % 10) + result;
    carry = Math.floor(sum / 10);
    i--;
    j--;
  }

  return result;
}

Time: O(m · n · max(m, n)) - m·n for the digit multiplications, plus a string addition of length up to m+n after each of the n digits · Space: O(m + n)

Optimal - Accumulate Into a Positions Array

Multiplying num1[i] by num2[j] always lands on positions i+j (its carry) and i+j+1 (its ones digit) of the final answer, regardless of the other digits. Accumulate every digit pair's product directly into a results array at those two positions, then read the array off as the final digit string.

function multiply(num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";

  const m = num1.length, n = num2.length;
  const digits = new Array(m + n).fill(0);

  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const product = Number(num1[i]) * Number(num2[j]);
      const sumPos = i + j + 1; // ones place of this product
      const carryPos = i + j;   // tens place of this product

      const total = digits[sumPos] + product;
      digits[sumPos] = total % 10;
      digits[carryPos] += Math.floor(total / 10);
    }
  }

  // Skip a single leading zero, if the result didn't need the full width
  let start = 0;
  while (start < digits.length - 1 && digits[start] === 0) {
    start++;
  }

  return digits.slice(start).join("");
}

Time: O(m · n) · Space: O(m + n)