Multiply Strings

Problem in simple words

Given two non-negative integers represented as strings, return their product as a string.

Core idea

The product of digits at i and j contributes to positions i + j and i + j + 1.

How the algorithm thinks

1. 1

   Prepare a zero-filled output array

   VISIT

   The output needs to be large enough to hold any possible product before any digit pair is multiplied.

   Watch: The initial zero-filled output array.

2. 2

   Multiply the current digit pair

   UPDATE

   Each digit from one number multiplied by each digit from the other contributes one piece of the final product.

   Watch: The current digit pair and their product.

3. 3

   Write the digit and carry into fixed offsets

   ADD

   The product's ones digit lands at one offset, while its carry lands at the neighboring offset, mirroring hand multiplication.

   Watch: The output array positions being updated.

4. 4

   Return the joined product

   RETURN

   Once every digit pair has contributed and carries have settled, the output array reads out as the final product.

   Watch: The final product string.

Step-by-step logic

• -Create an output array of zeros sized to the sum of both input lengths -- large enough for any possible product.
• -For every digit i in the first number and every digit j in the second number, compute their product plus whatever is already at output offset i+j+1.
• -Write that value's ones digit at offset i+j+1, and add its carry into offset i+j.
• -Once every digit pair has contributed, join the output array into a string and strip any leading zero.

Complexity

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

every pair of digits contributes once to the output array.

Implementation

This is the JavaScript implementation that generates the simulator timeline.

function multiply(input) {
  for every digit pair, add product into output offsets;
  normalize carries and join digits;
}

Common mistakes