Multiply Digit Chains

HardLinked List

Problem

A big-number library stores non-negative integers as linked lists of decimal digits, most significant digit first: 305 is [3, 0, 5].

Given two such lists a and b (no leading zeros except the number 0 itself), return their product in the same format, without leading zeros. Converting the whole number to a built-in integer type is not allowed.

Example 1

Input:
a = [1, 2, 3], b = [4, 5, 6]
Output:
[5, 6, 0, 8, 8]

123 × 456 = 56088.

Example 2

Input:
a = [0], b = [9, 9]
Output:
[0]

Anything times zero is a single 0, not [0, 0, 0].

Constraints

  • 1 ≤ nodes in each list ≤ 200
  • 0 ≤ node.val ≤ 9
  • No leading zeros, except the number 0 itself.

Hint

Show the first hint

200-digit numbers do not fit in 64 bits. How did you multiply by hand at school?

Walkthrough

How to approach it

01Clarify before coding

  • Can I use arbitrary-precision integers? No, that skips the whole exercise.
  • How long can the result be? At most n + m digits.
  • What if either factor is 0? Return a single [0].

02Brute force

Repeated addition: add a to itself b times using list addition.

Cost: Proportional to the value of b, which can be 10^200: impossible.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.