Multiply Strings

Problem Statement

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.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: num1 = "999", num2 = "999"
Output: "998001"

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

This problem simulates elementary school multiplication.

Key Insight

Position matters! When you multiply digit at position i with digit at position j, the result contributes to positions i+j and i+j+1.

Elementary School Method

Remember how we multiply multi-digit numbers:

    123
  ×  456
  ------
    738   (123 × 6)
   615    (123 × 5, shifted left)
  492     (123 × 4, shifted left twice)
  ------
  56088

Optimized Approach: Direct Position Calculation

Instead of creating intermediate arrays for each digit, we can directly calculate which positions each product contributes to!

Key Observation:

• num1 has length m
• num2 has length n
• Result has at most m + n digits
• When multiplying num1[i] × num2[j]:
  • Product goes to position i + j + 1
  • Carry goes to position i + j

Example: 123 × 456

Indices:  0 1 2
num1:     1 2 3
num2:     4 5 6

Result array: [0, 0, 0, 0, 0, 0]  (length 3 + 3 = 6)
Positions:     0  1  2  3  4  5

Multiply 3 (i=2) × 6 (j=2):
  Product = 18
  Position i+j+1 = 2+2+1 = 5
  Position i+j   = 2+2   = 4
  result[5] += 18 % 10 = 8
  result[4] += 18 / 10 = 1

Multiply 3 (i=2) × 5 (j=1):
  Product = 15
  Position i+j+1 = 2+1+1 = 4
  Position i+j   = 2+1   = 3
  result[4] += 15 % 10 = 5 (was 1, now 6)
  result[3] += 15 / 10 = 1
  ...

Algorithm Steps

1. Initialize result array of size m + n with zeros
2. Multiply each digit of num1 with each digit of num2
3. For each multiplication:
   • Calculate product = num1[i] × num2[j]
   • Add product to result[i+j+1]
   • Add carry to result[i+j]
4. Convert array to string, removing leading zeros

Why i+j and i+j+1?

Think about positions from the right (least significant):

• num1[i] is at position (m-1-i) from right
• num2[j] is at position (n-1-j) from right
• Product is at position (m-1-i) + (n-1-j) = m+n-2-i-j from right
• In array index: i+j+1 (ones place) and i+j (tens place)

Time & Space Complexity

• Time Complexity: O(m × n)

  • We multiply each digit of num1 with each digit of num2
  • m × n multiplications

• Space Complexity: O(m + n)

  • Result array of size m + n
  • Not counting output

Java Solution

class Solution {
    public String multiply(String num1, String num2) {
        // Edge cases
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int m = num1.length();
        int n = num2.length();
        int[] result = new int[m + n];

        // Multiply each digit
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int digit1 = num1.charAt(i) - '0';
                int digit2 = num2.charAt(j) - '0';
                int product = digit1 * digit2;

                // Position in result array
                int pos1 = i + j;
                int pos2 = i + j + 1;

                // Add to existing value at pos2
                int sum = product + result[pos2];

                // Update positions
                result[pos2] = sum % 10;
                result[pos1] += sum / 10;
            }
        }

        // Convert to string, skip leading zeros
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            if (!(sb.length() == 0 && num == 0)) {
                sb.append(num);
            }
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Python Solution

def multiply(num1: str, num2: str) -> str:
    # Edge cases
    if num1 == "0" or num2 == "0":
        return "0"

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

    # Multiply each digit
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            digit1 = int(num1[i])
            digit2 = int(num2[j])
            product = digit1 * digit2

            # Positions in result
            pos1 = i + j
            pos2 = i + j + 1

            # Add to existing value
            total = product + result[pos2]

            # Update positions
            result[pos2] = total % 10
            result[pos1] += total // 10

    # Convert to string, skip leading zeros
    result_str = ''.join(map(str, result))
    return result_str.lstrip('0') or '0'

Visual Example: 123 × 456

Step-by-step multiplication:

num1 = "123" (indices 0,1,2)
num2 = "456" (indices 0,1,2)
result = [0,0,0,0,0,0] (indices 0-5)

i=2, j=2: 3×6=18 → result[5]+=8, result[4]+=1 → [0,0,0,0,1,8]
i=2, j=1: 3×5=15 → result[4]+=5, result[3]+=1 → [0,0,0,1,6,8]
i=2, j=0: 3×4=12 → result[3]+=2, result[2]+=1 → [0,0,1,3,6,8]

i=1, j=2: 2×6=12 → result[4]+=2, result[3]+=1 → [0,0,1,4,8,8]
i=1, j=1: 2×5=10 → result[3]+=0, result[2]+=1 → [0,0,2,4,8,8]
i=1, j=0: 2×4=8  → result[2]+=8, result[1]+=0 → [0,0,10,4,8,8]
           (carry) → result[2]=0, result[1]+=1 → [0,1,0,4,8,8]

i=0, j=2: 1×6=6  → result[3]+=6, result[2]+=0 → [0,1,0,10,8,8]
           (carry) → result[3]=0, result[2]+=1 → [0,1,1,0,8,8]
i=0, j=1: 1×5=5  → result[2]+=5, result[1]+=0 → [0,1,6,0,8,8]
i=0, j=0: 1×4=4  → result[1]+=4, result[0]+=0 → [0,5,6,0,8,8]

Result: "56088"

Edge Cases

Zero Input

Input: num1 = "0", num2 = "9999"
Output: "0"

Must handle early!

Single Digit

Input: num1 = "9", num2 = "9"
Output: "81"

Large Numbers

Input: num1 = "999999999", num2 = "999999999"
Output: "999999998000000001"

This is why we can't use int/long!

Different Lengths

Input: num1 = "12", num2 = "9999"
Output: "119988"

Related Problems

• Add Strings (LeetCode 415): Addition instead of multiplication
• Add Binary (LeetCode 67): Binary addition
• Plus One (LeetCode 66): Increment large integer
• Multiply Strings (variations): Different bases
• String to Integer (atoi) (LeetCode 8): String to number conversion

Pattern Recognition

This problem demonstrates:

• Simulation of mathematical operations
• String manipulation
• Digit-by-digit processing
• Carry handling pattern
• Position/index mathematics

Common Mistakes

1. ❌ Using Integer.parseInt() or similar - violates constraints for large numbers
2. ❌ Wrong position calculation - confusing i+j vs i+j+1
3. ❌ Not handling leading zeros in result
4. ❌ Not handling zero inputs specially
5. ❌ Off-by-one errors in array indexing
6. ❌ Forgetting to handle carry properly
7. ❌ Wrong loop direction (should be right to left)

Tips for Interviews

• Explain the approach: Draw the elementary school multiplication
• Position formula: Clearly explain why i+j and i+j+1
• Draw an example: Use small numbers like 12 × 34
• Edge cases: Mention zero, single digit, large numbers
• Why can't use int: Numbers can be up to 200 digits!
• Optimization: This is already optimal for string multiplication
• Alternative: Could do Karatsuba or FFT, but much more complex

Follow-Up Questions

1. Q: Can you optimize below O(m×n)?

   • A: Yes! Karatsuba algorithm is O(n^1.58), FFT is O(n log n), but very complex

2. Q: What if inputs are in different bases?

   • A: Similar approach, adjust modulo and division operations

3. Q: How to handle negative numbers?

   • A: Track signs separately, multiply absolute values, apply sign at end

4. Q: What about very large numbers (millions of digits)?

   • A: Use FFT-based multiplication or specialized libraries

Comparison with Addition

| Operation | Time | Carry Direction | Complexity | |-----------|------|-----------------|------------| | Add Strings | O(max(m,n)) | Right to left | Simpler | | Multiply Strings | O(m×n) | Right to left | More complex |

Why This Problem?

Tests understanding of:

• Basic arithmetic simulation
• Array manipulation
• Index mathematics
• Handling large numbers without BigInteger
• Edge case handling

This is a fundamental problem for implementing arbitrary-precision arithmetic!