Multiply Two Numbers Represented as Strings

Problem

Multiply two non-negative integers represented as strings, and return the product as a string, without converting the entire input to a native integer type.

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

Python Solution

def multiply_strings(num1, num2):
    if num1 == "0" or num2 == "0":
        return "0"
    m, n = len(num1), len(num2)
    result = [0] * (m + n)
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = int(num1[i]) * int(num2[j])
            pos_low, pos_high = i + j + 1, i + j
            total = mul + result[pos_low]
            result[pos_low] = total % 10
            result[pos_high] += total // 10
    result_str = "".join(map(str, result)).lstrip("0")
    return result_str

C++ Solution

string multiplyStrings(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    int m = num1.size(), n = num2.size();
    vector<int> result(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 posLow = i + j + 1, posHigh = i + j;
            int total = mul + result[posLow];
            result[posLow] = total % 10;
            result[posHigh] += total / 10;
        }
    }
    string resultStr;
    for (int digit : result) {
        if (!(resultStr.empty() && digit == 0)) resultStr += to_string(digit);
    }
    return resultStr.empty() ? "0" : resultStr;
}

Java Solution

class Solution {
    public String multiplyStrings(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int m = num1.length(), n = num2.length();
        int[] result = 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 posLow = i + j + 1, posHigh = i + j;
                int total = mul + result[posLow];
                result[posLow] = total % 10;
                result[posHigh] += total / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int digit : result) {
            if (!(sb.length() == 0 && digit == 0)) sb.append(digit);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Complexity

Time: O(m · n) — every pair of digits, one from each number, contributes exactly one multiplication. Space: O(m + n) for the result digit array, matching the maximum possible length of the product.