View on NeetCode
View on LeetCode

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.

Example 1:

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

Example 2:

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

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 1: Grade School Multiplication

The key insight is to simulate grade school multiplication: multiply each digit of num2 with num1, then sum the results with appropriate positioning.

Implementation

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        # Result can be at most len(num1) + len(num2) digits
        result = [0] * (len(num1) + len(num2))

        # Reverse both numbers for easier processing
        num1 = num1[::-1]
        num2 = num2[::-1]

        # Multiply each digit
        for i in range(len(num1)):
            for j in range(len(num2)):
                digit1 = int(num1[i])
                digit2 = int(num2[j])

                # Multiply digits and add to appropriate position
                result[i + j] += digit1 * digit2

                # Handle carry
                result[i + j + 1] += result[i + j] // 10
                result[i + j] %= 10

        # Remove leading zeros
        while len(result) > 1 and result[-1] == 0:
            result.pop()

        # Convert to string and reverse
        return ''.join(map(str, result[::-1]))

Approach 2: Optimized Position Calculation

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

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

        # Process from right to left (no need to reverse)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                # Calculate positions
                p1 = i + j
                p2 = i + j + 1

                # Multiply and add to existing value
                mul = int(num1[i]) * int(num2[j])
                total = mul + result[p2]

                result[p2] = total % 10
                result[p1] += total // 10

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

Approach 3: String Builder Approach

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        def add_strings(s1, s2):
            """Helper function to add two number strings"""
            result = []
            carry = 0
            i, j = len(s1) - 1, len(s2) - 1

            while i >= 0 or j >= 0 or carry:
                digit1 = int(s1[i]) if i >= 0 else 0
                digit2 = int(s2[j]) if j >= 0 else 0

                total = digit1 + digit2 + carry
                result.append(str(total % 10))
                carry = total // 10

                i -= 1
                j -= 1

            return ''.join(result[::-1])

        result = "0"

        # Multiply num1 with each digit of num2
        for i in range(len(num2) - 1, -1, -1):
            digit = int(num2[i])
            carry = 0
            temp = []

            # Multiply num1 with single digit
            for j in range(len(num1) - 1, -1, -1):
                product = int(num1[j]) * digit + carry
                temp.append(str(product % 10))
                carry = product // 10

            if carry:
                temp.append(str(carry))

            # Add appropriate zeros for position
            temp_str = ''.join(temp[::-1]) + '0' * (len(num2) - 1 - i)
            result = add_strings(result, temp_str)

        return result

Complexity Analysis

• Time Complexity: O(m × n), where m and n are the lengths of num1 and num2. We multiply each digit pair once.
• Space Complexity: O(m + n) for storing the result.

Key Insights

1. Position Mapping: When multiplying digits at positions i and j, the result contributes to positions i+j and i+j+1.

2. Maximum Length: Product of m-digit and n-digit numbers has at most m+n digits.

3. Carry Handling: Process carries after each multiplication or handle them in a separate pass.

4. Leading Zeros: Remember to remove leading zeros from the final result.

5. Index Math: For digits at indices i and j (from right), product affects positions [i+j, i+j+1].

6. Zero Edge Case: If either input is “0”, result is “0” immediately.

7. Grade School Method: This mimics how we multiply numbers by hand: multiply each digit pair and sum with proper alignment.