Code Implementation

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        res = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                sum_ = mul + res[i + j + 1]
                res[i + j + 1] = sum_ % 10
                res[i + j] += sum_ // 10
        result = []
        for num in res:
            if not (len(result) == 0 and num == 0):
                result.append(str(num))
        return ''.join(result)
      

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        int m = num1.size(), n = num2.size();
        vector<int> res(m + n, 0);
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int sum = mul + res[i + j + 1];
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }
        string result;
        int i = 0;
        while (i < res.size() && res[i] == 0) ++i;
        for (; i < res.size(); ++i) result.push_back(res[i] + '0');
        return result;
    }
};
      

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int m = num1.length(), n = num2.length();
        int[] res = new int[m + n];
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = mul + res[i + j + 1];
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < res.length && res[i] == 0) i++;
        for (; i < res.length; i++) sb.append(res[i]);
        return sb.toString();
    }
}
      

var multiply = function(num1, num2) {
    if (num1 === "0" || num2 === "0") return "0";
    let m = num1.length, n = num2.length;
    let res = new Array(m + n).fill(0);
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            let mul = (num1.charCodeAt(i) - 48) * (num2.charCodeAt(j) - 48);
            let sum = mul + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += Math.floor(sum / 10);
        }
    }
    let result = "";
    for (let num of res) {
        if (!(result.length === 0 && num === 0)) {
            result += num;
        }
    }
    return result;
};
      

Problem Description

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

Key constraints:

• You must not use built-in libraries for handling large integers (e.g., BigInteger).
• You are not allowed to convert the entire input strings directly to integers.
• Both num1 and num2 will only contain digits (0-9).
• Both numbers are non-negative and do not contain any leading zeroes, except for "0" itself.
• The output should not contain leading zeros unless the result is "0".

Thought Process

At first glance, multiplying two numbers seems straightforward, especially when programming languages provide built-in operations for arithmetic. However, the key challenge here is that the numbers are provided as strings and may be too large to fit into standard integer types.

The brute-force approach might be to convert the strings to integers, multiply them, and convert the result back to a string. However, this is explicitly disallowed by the problem constraints. Therefore, we need to simulate the multiplication process manually, just as we do by hand on paper.

The manual multiplication process involves multiplying each digit of one number by each digit of the other, keeping track of carries, and summing the results in the correct positions. This approach avoids the limitations of integer overflow and works for arbitrarily large numbers.

As we optimize, we realize that we can pre-allocate an array to hold the intermediate results, which allows us to efficiently sum up the partial products and handle carries in a single pass.

Solution Approach

To multiply two numbers represented as strings without converting them to integers, we simulate the digit-by-digit multiplication process. Here’s how we can do it:

1. Initialize a result array:
   • If num1 has m digits and num2 has n digits, the maximum number of digits in the product is m + n.
   • We create an array res of size m + n, initialized to zero, to store the intermediate results.
2. Multiply each digit:
   • We iterate over each digit in num1 and num2 from right to left (least significant to most significant).
   • For each pair of digits, we multiply them and add the product to the corresponding position in res.
   • The position in res for the product of num1[i] and num2[j] is i + j + 1, with any carry added to i + j.
3. Handle carry over:
   • After adding the product, we update the current position with sum % 10 and add sum // 10 to the next left position.
4. Build the final result string:
   • After all multiplications, we may have leading zeros in res. We skip these when building the final string.
   • If the result is all zeros, we return "0". Otherwise, we concatenate the digits to form the answer.

This approach mimics the traditional long multiplication method and efficiently handles very large numbers.

Example Walkthrough

Let's take an example: num1 = "123", num2 = "45"

• Step 1: Initialize res = [0, 0, 0, 0, 0] (since 3 + 2 = 5)
• Step 2: Multiply each digit:
  • i = 2 (num1[2]='3') x j = 1 (num2[1]='5'): 3*5=15, add to res[4], res[4]=5, carry=1 to res[3]
  • i = 2 x j = 0: 3*4=12, add to res[3]=1+12=13, res[3]=3, carry=1 to res[2]
  • i = 1 (num1[1]='2') x j = 1: 2*5=10, add to res[3]=3+10=13, res[3]=3, carry=1 to res[2]
  • i = 1 x j = 0: 2*4=8, add to res[2]=1+8=9, res[2]=9
  • i = 0 (num1[0]='1') x j = 1: 1*5=5, add to res[2]=9+5=14, res[2]=4, carry=1 to res[1]
  • i = 0 x j = 0: 1*4=4, add to res[1]=1+4=5, res[1]=5

  After all steps, res = [0, 5, 5, 3, 5]

• Step 3: Skip leading zero, join the rest: "5535"

The answer is "5535", which matches 123 × 45 = 5535.

Time and Space Complexity

• Brute-force Approach:
  • Converting strings to integers and multiplying: O(1) for small numbers, but not allowed for large numbers or by the problem constraints.
• Optimized Approach (Manual Multiplication):
  • Time Complexity: O(m * n), where m and n are the lengths of num1 and num2. This is because we multiply every digit of num1 with every digit of num2.
  • Space Complexity: O(m + n), for the result array to store the intermediate and final results.

The optimized approach is efficient and scalable for very large numbers represented as strings.

Summary

In this problem, we are asked to multiply two large numbers represented as strings without using built-in big integer libraries or converting the strings directly to integers. The key insight is to simulate the manual multiplication process by using an array to store intermediate results and properly handle carries. This approach is both intuitive and efficient, allowing us to multiply numbers of arbitrary length with O(m * n) time and O(m + n) space complexity. The solution elegantly mirrors the way multiplication is performed by hand, making it both robust and easy to understand.