#43

Medium

LeetCode Problem Workspace

Multiply Strings

Multiply Strings requires simulating integer multiplication using only string operations without direct numeric conversion or BigInteger libraries.

math string simulation

Problem Statement

You are given two non-negative integers num1 and num2 represented as strings. Compute the product of these two numbers and return it as a string without converting the inputs directly to integers or using any built-in BigInteger library.

Each string contains only digits and does not include leading zeros except for the single digit zero. Implement a solution that handles all digit combinations efficiently, simulating the multiplication process digit by digit as done manually on paper.

Examples

Example 1

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

Output: "6"

Example details omitted.

Example 2

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

Output: "56088"

Example details omitted.

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.

Solution Approach

Reverse and Prepare Arrays

Convert both num1 and num2 into reversed arrays of digits so that multiplication starts from the least significant digit. This setup allows proper carry propagation in a simulation of manual multiplication.

Simulate Column Multiplication

Iterate through each digit of num1 and num2, multiplying and adding to the appropriate index in a result array. Accumulate carries after each multiplication to maintain correct values, ensuring each position represents a single digit.

Convert Result Array to String

Trim any leading zeros from the result array and join digits into a single string. If the array is empty after trimming, return "0". This final step completes the string-only multiplication simulation.

Complexity Analysis

Metric	Value
Time	O(M \cdot N)
Space	O(M + N)

Time complexity is O(M * N) because each digit in num1 multiplies with each digit in num2. Space complexity is O(M + N) to store intermediate results in the result array representing the product of M and N digit numbers.

What Interviewers Usually Probe

Check if the candidate handles carry propagation correctly in a digit-by-digit simulation.
Watch for attempts to convert strings directly to integers, which violates constraints.
Assess whether the candidate efficiently manages the result array without unnecessary string concatenations.

Common Pitfalls or Variants

Common pitfalls

Failing to reverse the input strings before multiplying can misalign digits and produce incorrect results.
Ignoring carry propagation leads to digits exceeding 9 and incorrect final products.
Returning partial results or failing to remove leading zeros may cause format errors in the output string.

Follow-up variants

Multiply Strings using recursive divide-and-conquer instead of iterative simulation for large digit inputs.
Implement multiplication with memory optimization to reduce the intermediate array size to a minimal representation.
Handle negative numbers represented as strings, extending the simulation to include sign management.

FAQ

Can I use built-in integer conversion for Multiply Strings?

No, using direct integer conversion or BigInteger libraries violates the problem constraints; the solution must simulate multiplication purely with strings.

What is the recommended approach to handle carries in Multiply Strings?

Use a result array where each index accumulates products and carry values, updating sequentially to maintain correct single-digit positions.

How does reversing input strings help in the Multiply Strings solution?

Reversing allows starting multiplication from the least significant digit, aligning with manual column multiplication and simplifying carry propagation.

What should be returned if one of the inputs is "0"?

If either input is "0", the correct result is simply "0" since any number multiplied by zero is zero.

Can this approach handle very long strings up to 200 digits?

Yes, the O(M * N) time complexity and O(M + N) space complexity are designed to handle the maximum input lengths efficiently.

terminal

Solution

Solution 1: Simulating Mathematical Multiplication

Assume the lengths of $num1$ and $num2$ are $m$ and $n$ respectively, then the length of their product can be at most $m + n$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        arr = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            a = int(num1[i])
            for j in range(n - 1, -1, -1):
                b = int(num2[j])
                arr[i + j + 1] += a * b
        for i in range(m + n - 1, 0, -1):
            arr[i - 1] += arr[i] // 10
            arr[i] %= 10
        i = 0 if arr[0] else 1
        return "".join(str(x) for x in arr[i:])

Continue Practicing

#67 add binary #412 fizz buzz #415 add strings