Problem Description

You are given two non-negative integers represented as strings, num1 and num2. Your task is to multiply these two numbers and return their product as a string.

The key constraint is that you cannot use any built-in BigInteger library or convert the strings directly to integers. This means you need to implement the multiplication algorithm manually, working with the string representations digit by digit.

For example:

• If num1 = "2" and num2 = "3", the output should be "6"
• If num1 = "123" and num2 = "456", the output should be "56088"

The solution simulates the traditional grade-school multiplication method. When multiplying two numbers with m and n digits respectively, the product will have at most m + n digits. The algorithm:

1. Creates an array of size m + n to store intermediate results
2. Multiplies each digit of num1 with each digit of num2, placing the result at the appropriate position in the array
3. Handles carry-over operations by iterating through the array from right to left
4. Converts the final array back to a string, removing any leading zeros

The key insight is that when multiplying digit at position i in num1 with digit at position j in num2, the result contributes to position i + j + 1 in the result array (using 0-based indexing from the left).

Intuition

Think about how you learned to multiply large numbers by hand in elementary school. When you multiply 123 × 456, you would:

1. Multiply 123 by 6, getting 738
2. Multiply 123 by 5, getting 615, but shift it one position left (add a zero)
3. Multiply 123 by 4, getting 492, but shift it two positions left (add two zeros)
4. Add all these intermediate results together

The key observation is that each digit multiplication contributes to a specific position in the final result. When we multiply the digit at position i from the first number with the digit at position j from the second number, where do we place this result?

Consider multiplying num1[i] × num2[j]:

• num1[i] represents a digit at the (m-1-i)-th power of 10 from the right
• num2[j] represents a digit at the (n-1-j)-th power of 10 from the right
• Their product contributes to the (m-1-i) + (n-1-j) = (m+n-2-i-j)-th power of 10 from the right

In array terms (0-indexed from left), this maps to position i + j + 1 in our result array.

Why do we need an array of size m + n? The smallest product would be 10^(m-1) × 10^(n-1) = 10^(m+n-2) (like 100 × 100 = 10000), which has m + n - 1 digits. The largest would be (10^m - 1) × (10^n - 1) (like 999 × 999 = 998001), which could have m + n digits. So m + n is the maximum possible length.

By processing from right to left (least significant to most significant digit) and handling carries naturally through integer division and modulo operations, we simulate the exact process of manual multiplication while avoiding integer overflow issues that would occur if we tried to convert the entire strings to numbers.

Learn more about Math patterns.

Solution Approach

The implementation follows the mathematical multiplication simulation approach. Let's walk through the algorithm step by step:

1. Handle Edge Cases

if num1 == "0" or num2 == "0":
    return "0"

If either number is zero, the product is zero. This early return optimizes the edge case.

2. Initialize Result Array

m, n = len(num1), len(num2)
arr = [0] * (m + n)

We create an array of size m + n to store the intermediate multiplication results. This array will hold each digit of the final product.

3. Perform Digit-by-Digit Multiplication

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

We iterate through both numbers from right to left (least significant to most significant digit). For each pair of digits:

• Convert the character digits to integers
• Multiply them together
• Add the result to position i + j + 1 in the array

The key insight is the position formula: when multiplying digit at index i in num1 with digit at index j in num2, the result goes to position i + j + 1. This is because:

• If num1 has m digits and num2 has n digits
• The digit at position i represents 10^(m-1-i)
• The digit at position j represents 10^(n-1-j)
• Their product contributes to 10^(m-1-i+n-1-j) = 10^(m+n-2-i-j)
• In our 0-indexed array from the left, this maps to position i + j + 1

4. Handle Carries

for i in range(m + n - 1, 0, -1):
    arr[i - 1] += arr[i] // 10
    arr[i] %= 10

After all multiplications, some positions might have values greater than 9. We process the array from right to left:

• The carry (arr[i] // 10) is added to the previous position
• The current position keeps only the ones digit (arr[i] % 10)

5. Convert to String and Remove Leading Zeros

i = 0 if arr[0] else 1
return "".join(str(x) for x in arr[i:])

Finally, we convert the array to a string. If the first element is 0 (which happens when the product doesn't need all m + n digits), we start from index 1 to avoid leading zeros.

The time complexity is O(m × n) as we multiply each digit of num1 with each digit of num2. The space complexity is O(m + n) for storing the result array.

Example Walkthrough

Let's walk through multiplying num1 = "123" and num2 = "45" step by step.

Step 1: Initialize

• m = 3 (length of "123"), n = 2 (length of "45")
• Create result array: arr = [0, 0, 0, 0, 0] (size m + n = 5)

Step 2: Digit-by-Digit Multiplication

We'll multiply each digit, starting from the rightmost digits:

Round 1: i = 2 (digit '3' from "123")

• j = 1: Multiply 3 × 5 = 15, add to arr[2+1+1] = arr[4]
  • arr = [0, 0, 0, 0, 15]
• j = 0: Multiply 3 × 4 = 12, add to arr[2+0+1] = arr[3]
  • arr = [0, 0, 0, 12, 15]

Round 2: i = 1 (digit '2' from "123")

• j = 1: Multiply 2 × 5 = 10, add to arr[1+1+1] = arr[3]
  • arr = [0, 0, 0, 22, 15] (12 + 10 = 22)
• j = 0: Multiply 2 × 4 = 8, add to arr[1+0+1] = arr[2]
  • arr = [0, 0, 8, 22, 15]

Round 3: i = 0 (digit '1' from "123")

• j = 1: Multiply 1 × 5 = 5, add to arr[0+1+1] = arr[2]
  • arr = [0, 0, 13, 22, 15] (8 + 5 = 13)
• j = 0: Multiply 1 × 4 = 4, add to arr[0+0+1] = arr[1]
  • arr = [0, 4, 13, 22, 15]

Step 3: Handle Carries

Process from right to left to propagate carries:

• Position 4: arr[4] = 15

  • Carry: 15 ÷ 10 = 1 → add to arr[3]
  • Keep: 15 % 10 = 5
  • arr = [0, 4, 13, 23, 5]

• Position 3: arr[3] = 23

  • Carry: 23 ÷ 10 = 2 → add to arr[2]
  • Keep: 23 % 10 = 3
  • arr = [0, 4, 15, 3, 5]

• Position 2: arr[2] = 15

  • Carry: 15 ÷ 10 = 1 → add to arr[1]
  • Keep: 15 % 10 = 5
  • arr = [0, 5, 5, 3, 5]

• Position 1: arr[1] = 5

  • Carry: 5 ÷ 10 = 0 → add to arr[0]
  • Keep: 5 % 10 = 5
  • arr = [0, 5, 5, 3, 5]

Step 4: Convert to String

• First element is 0, so start from index 1
• Join arr[1:] = [5, 5, 3, 5] → "5535"

Verification: 123 × 45 = 5535 ✓

The key insight is how the position formula i + j + 1 correctly places each partial product. For instance, when we multiply the ones digit of "123" (position 2) with the tens digit of "45" (position 0), we get 3 × 4 = 12, which contributes to the tens place of the result (position 3 in our array).

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of num1 and n is the length of num2. This is because the algorithm uses nested loops where the outer loop iterates through all m digits of num1 (from index m-1 to 0), and for each digit, the inner loop iterates through all n digits of num2 (from index n-1 to 0). Each iteration performs a constant-time operation of multiplying two single digits and adding to the result array, resulting in m × n total operations.

The space complexity is O(m + n). The algorithm creates an array arr of size m + n to store the intermediate and final results of the multiplication. This array size is determined by the maximum possible length of the product of two numbers, which is at most m + n digits (for example, 99 × 99 = 9801, where two 2-digit numbers produce a 4-digit result). The final string conversion also takes O(m + n) space, but this doesn't change the overall space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Position Mapping When Placing Multiplication Results

One of the most common mistakes is incorrectly calculating where to place the product of two digits in the result array. Many developers mistakenly use arr[i + j] instead of arr[i + j + 1].

Why this happens: The confusion arises from mixing up 0-based indexing with the mathematical significance of digit positions.

Incorrect approach:

# Wrong: This will place results in wrong positions
for i in range(m - 1, -1, -1):
    for j in range(n - 1, -1, -1):
        arr[i + j] += int(num1[i]) * int(num2[j])  # Wrong position!

Correct approach:

# Correct: Use i + j + 1 for proper position mapping
for i in range(m - 1, -1, -1):
    for j in range(n - 1, -1, -1):
        arr[i + j + 1] += int(num1[i]) * int(num2[j])

2. Forgetting to Handle Multiple Leading Zeros

While the provided solution handles a single leading zero, a more robust approach should handle edge cases where the result might have multiple leading zeros (though mathematically this shouldn't happen with valid inputs).

Potential issue:

# This only checks if the first element is 0
start_index = 0 if result[0] != 0 else 1

More robust solution:

# Find the first non-zero digit
start_index = 0
while start_index < len(result) - 1 and result[start_index] == 0:
    start_index += 1

3. Processing Carries in the Wrong Direction

Another common mistake is processing carries from left to right instead of right to left, which can lead to incorrect propagation of carry values.

Wrong direction:

# Incorrect: Processing from left to right
for i in range(1, m + n):
    arr[i] += arr[i - 1] // 10  # This won't work correctly
    arr[i - 1] %= 10

Correct direction:

# Correct: Processing from right to left
for i in range(m + n - 1, 0, -1):
    arr[i - 1] += arr[i] // 10
    arr[i] %= 10

4. Not Handling the Edge Case of "0" Properly

Failing to check for zero inputs at the beginning can lead to unnecessary computation and potential issues with the final string conversion.

Issue without zero check:

def multiply(self, num1: str, num2: str) -> str:
    # Without checking for "0", we might get "00" or "000" as output
    m, n = len(num1), len(num2)
    result = [0] * (m + n)
    # ... multiplication logic ...
    # This could return "00" for "0" × "10"

Solution: Always check for zero inputs at the beginning:

if num1 == "0" or num2 == "0":
    return "0"

5. Integer Overflow in Other Languages

While Python handles arbitrary precision integers automatically, in languages like Java or C++, storing a * b directly might cause overflow for large digits multiplication plus existing value.

Potential overflow in other languages:

// In C++, this might overflow for large accumulated values
result[i + j + 1] += digit1 * digit2;

Safe approach for other languages:

// Break down the operation to avoid overflow
int product = digit1 * digit2;
int sum = result[i + j + 1] + product;
result[i + j + 1] = sum % 10;
result[i + j] += sum / 10;