Multiply Numbers Written as Text

MediumMath & Geometry

Problem

Two non-negative integers first and second are given as decimal strings with up to a thousand digits each.

Return their product as a decimal string without leading zeros. Do not convert the inputs to big integers.

Example 1

Input:
first = "12", second = "34"
Output:
"408"

Example 2

Input:
first = "999", second = "0"
Output:
"0"

Leading zeros must be stripped, but a zero result is still "0".

Example 3

Input:
first = "123456789123456789", second = "987654321987654321"
Output:
"121932631356500531347203169112635269"

Constraints

  • 1 ≤ first.length, second.length ≤ 1000
  • Digits only, no leading zeros except the number "0" itself

Hint

Show the first hint

Long multiplication on paper multiplies every digit of one number by every digit of the other.

Walkthrough

How to approach it

01Clarify before coding

  • Can either number be 0? Yes; the answer must be "0", not a run of zeros.
  • How long can the result be? At most n + m digits.
  • Is O(n · m) acceptable? Yes for 1000 digits each; faster methods (Karatsuba, FFT) exist but are not expected.

02Brute force

Add first to itself second times using string addition.

Cost: O(value of second · n): with a 1000-digit multiplier that is about 10^1000 additions.

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.