Skip to main content

43. Multiply Strings

medium

Multiply two non-negative integers represented as strings, returning the product as a string. The textbook grade-school O(m*n) multiplication problem — with the index-mapping insight that nums[i] * nums[j] lands at positions [i + j, i + j + 1].

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Constraints

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.
  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Early exit: if either is '0', return '0'.

Hint 2

Index insight: multiplying num1[i] (digit at index i from the LEFT) by num2[j] produces a value that lands at result positions i + j (carry) and i + j + 1 (units).

Hint 3

Allocate an int array result of length m + n filled with 0. Loop i from m-1 down to 0, j from n-1 down to 0. Compute mul = (num1[i]-'0') * (num2[j]-'0') + result[i + j + 1]. result[i + j + 1] = mul % 10; result[i + j] += mul / 10.

Hint 4

Walk result from left to right; strip leading zeros; convert digits to characters and return.

Solution approach

Reveal approach

Allocate an int array result of length m + n initialized to 0. The key indexing fact: num1[i] * num2[j] contributes a two-digit value (at most 81) that lands at result[i + j] (carry digit) and result[i + j + 1] (units digit). Double loop: for i from m-1 down to 0, for j from n-1 down to 0: mul = (num1[i] - '0') * (num2[j] - '0') + result[i + j + 1]; result[i + j + 1] = mul % 10; result[i + j] += mul / 10. The += handles carry from previous (i, j+1) iterations correctly because we process j right-to-left. After the loop, skip any leading zeros in result, convert remaining digits to a string. Handle empty result -> '0'. O(m * n) time, O(m + n) space.

Complexity

Time
O(m * n)
Space
O(m + n)

Related patterns

  • math
  • string-scan

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

More Math practice problems

See all Math problems →