Multiply Strings

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazonMicrosoftMeta

Problem Description

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”

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.

Digit Placement Indexing

An input string of length 200 is too large to fit inside standard 64-bit integer variables. We must implement long multiplication manually.

For two numbers of length N and M, the maximum length of their product is N + M. We initialize a results array of size N + M with zeros.

When multiplying digit num1[i] (from right to left) and num2[j] (from right to left):

The product mul = num1[i] * num2[j] will contribute to positions i + j and i + j + 1 in the results array:
- sum = mul + results[i + j + 1]
- results[i + j + 1] = sum % 10
- results[i + j] += sum / 10 (carry over to the next position)

Solution: Digit Indexing Grid

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

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

        for (int i = n - 1; i >= 0; i--) {
            int d1 = num1.charAt(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int d2 = num2.charAt(j) - '0';
                int mul = d1 * d2;
                int sum = mul + pos[i + j + 1];

                pos[i + j + 1] = sum % 10;
                pos[i + j] += sum / 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int p : pos) {
            if (!(sb.length() == 0 && p == 0)) { // skip leading zeros
                sb.append(p);
            }
        }

        return sb.toString();
    }
}

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

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

        for i in range(n - 1, -1, -1):
            d1 = int(num1[i])
            for j in range(m - 1, -1, -1):
                d2 = int(num2[j])
                mul = d1 * d2
                total = mul + pos[i + j + 1]

                pos[i + j + 1] = total % 10
                pos[i + j] += total // 10

        # construct result skipping leading zeros
        result = []
        for p in pos:
            if not (len(result) == 0 and p == 0):
                result.append(str(p))

        return "".join(result)

#include <string>
#include <vector>

class Solution {
public:
    std::string multiply(std::string num1, std::string num2) {
        if (num1 == "0" || num2 == "0") return "0";

        int n = num1.size(), m = num2.size();
        std::vector<int> pos(n + m, 0);

        for (int i = n - 1; i >= 0; i--) {
            int d1 = num1[i] - '0';
            for (int j = m - 1; j >= 0; j--) {
                int d2 = num2[j] - '0';
                int mul = d1 * d2;
                int sum = mul + pos[i + j + 1];

                pos[i + j + 1] = sum % 10;
                pos[i + j] += sum / 10;
            }
        }

        std::string result = "";
        for (int p : pos) {
            if (!(result.empty() && p == 0)) {
                result += std::to_string(p);
            }
        }

        return result;
    }
};

Complexity Analysis:

Time Complexity: O(N * M) where N and M are the lengths of num1 and num2.
Space Complexity: O(N + M) to store the product digits.