Skip to main content
CodePeetCodePeet
CodePeet 150

Multiply Strings

MEDIUMProblemSolveExternal Links

Description

Given two non-negative integers num1 and num2 represented as strings, return their product, also represented as a string.

You are not allowed to use any built-in big-integer library or convert the input strings directly to integers.

In simpler terms: Imagine you are given two very large numbers written on paper — so large that they don't fit into a standard integer variable. Your job is to multiply them together the same way you would by hand on paper, digit by digit, and produce the result as a string of digits.

Examples

Example 1

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

Output: "6"

Explanation: The product of 2 and 3 is 6. Since both inputs are single-digit numbers, the multiplication is straightforward.

Example 2

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

Output: "56088"

Explanation: Multiplying 123 × 456 gives 56088. This is computed by multiplying each digit of one number by each digit of the other and summing partial products with proper positional shifts — exactly like long multiplication on paper.

Example 3

Input: num1 = "0", num2 = "52"

Output: "0"

Explanation: Any number multiplied by zero is zero. This is an important edge case to handle — the result should be "0", not "00" or an empty string.

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

Editorial

Brute Force

Intuition

The most natural way to think about multiplying two numbers is how we learned it in elementary school: repeated addition. Multiplication is simply adding one number to itself repeatedly.

For example, 123 × 4 means adding 123 four times: 123 + 123 + 123 + 123 = 492.

We can extend this to multi-digit multipliers by breaking them down: 123 × 456 = 123 × 400 + 123 × 50 + 123 × 6. But even the simpler interpretation — add num1 to itself num2 times — captures the brute force idea.

Since we cannot convert strings to integers directly, we need a helper function that adds two number-strings together. Then we loop num2 times, adding num1 to a running total each iteration.

The problem with this approach is clear: if num2 is a 200-digit number, we'd need to perform an astronomically large number of additions — far too many to ever complete.

Step-by-Step Explanation

Let's trace through with num1 = "12", num2 = "3":

Step 1: Initialize result = "0".

Step 2: Iteration 1: result = addStrings("0", "12") = "12".

Step 3: Iteration 2: result = addStrings("12", "12") = "24".

Step 4: Iteration 3: result = addStrings("24", "12") = "36".

Step 5: num2 exhausted (3 iterations). Return "36".

This works for small numbers, but for num2 = "999..." (200 digits), we'd need ~10^200 iterations — completely infeasible.

Algorithm

  1. Implement a helper function addStrings(a, b) that adds two number-strings digit by digit with carry.
  2. Initialize result = "0".
  3. Convert num2 to an iteration count (conceptually — since we can't convert to int for large numbers, this approach is inherently limited).
  4. Loop num2 times: result = addStrings(result, num1).
  5. Return result.

Code

#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    string addStrings(string a, string b) {
        string result;
        int carry = 0;
        int i = a.size() - 1, j = b.size() - 1;
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            result += (char)('0' + sum % 10);
            carry = sum / 10;
        }
        reverse(result.begin(), result.end());
        return result;
    }
    
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        
        // This approach only works for small num2 values
        // For demonstration, we convert num2 to int (violates constraint for large inputs)
        string result = "0";
        int times = stoi(num2); // Only works for small num2
        for (int i = 0; i < times; i++) {
            result = addStrings(result, num1);
        }
        return result;
    }
};
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        
        def add_strings(a: str, b: str) -> str:
            result = []
            carry = 0
            i, j = len(a) - 1, len(b) - 1
            while i >= 0 or j >= 0 or carry:
                total = carry
                if i >= 0:
                    total += int(a[i])
                    i -= 1
                if j >= 0:
                    total += int(b[j])
                    j -= 1
                result.append(str(total % 10))
                carry = total // 10
            return ''.join(reversed(result))
        
        # Only works for small num2 values
        result = "0"
        times = int(num2)  # Violates constraint for large inputs
        for _ in range(times):
            result = add_strings(result, num1)
        return result
class Solution {
    private String addStrings(String a, String b) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            result.append((char) ('0' + sum % 10));
            carry = sum / 10;
        }
        return result.reverse().toString();
    }
    
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        
        // Only works for small num2 values
        String result = "0";
        int times = Integer.parseInt(num2); // Violates constraint for large inputs
        for (int i = 0; i < times; i++) {
            result = addStrings(result, num1);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(num2 × m)

Where num2 is the numeric value of the second string and m is the length of num1. We perform num2 string additions, each of which takes O(m) time for digit-by-digit addition. If num2 is a 200-digit number, num2 can be up to 10^200 — making this approach completely infeasible.

Space Complexity: O(m + n)

The result string can be at most m + n digits long. Each addition also uses O(m) temporary space.

Why This Approach Is Not Efficient

The repeated addition approach has a fatal flaw: the number of iterations depends on the numeric value of num2, not its length. With num2 up to 200 digits long, its numeric value can be as large as 10^200 — a number with 200 zeros. Even at a billion operations per second, this would take longer than the age of the universe.

The fundamental problem is that we're treating multiplication as iterated addition, which doesn't scale. We need an approach where the work depends on the number of digits (at most 200), not the numeric magnitude (up to 10^200).

The key insight: recall how you multiply on paper. You don't add 456 times. Instead, you multiply each digit of the bottom number by each digit of the top number, placing partial results at the correct position. This digit-by-digit approach does at most m × n single-digit multiplications — at most 200 × 200 = 40,000 operations. That's the approach we need.

Optimal Approach - Grade School Multiplication (Digit-by-Digit)

Intuition

Think back to how you multiply numbers by hand on paper. To compute 123 × 456, you would:

  1. Multiply 123 by 6 (ones digit of 456) → 738, write it starting at position 0.
  2. Multiply 123 by 5 (tens digit of 456) → 615, write it starting at position 1 (shifted left by one).
  3. Multiply 123 by 4 (hundreds digit of 456) → 492, write it starting at position 2 (shifted left by two).
  4. Add all three partial products together.

The crucial observation is: when you multiply digit num1[i] by digit num2[j], the result contributes to positions i + j and i + j + 1 in the final answer (counting positions from the most significant end).

More precisely, if we index both strings from the right (least significant digit), then the product of num1[i] and num2[j] lands at position i + j in a result array. We accumulate all such products, handle carries, and convert back to a string.

This is exactly what a result array of length m + n captures: the maximum possible length of the product of an m-digit number and an n-digit number is m + n digits (for example, 99 × 99 = 9801, which is 4 digits = 2 + 2).

Step-by-Step Explanation

Let's trace through with num1 = "12", num2 = "34" using the standard positional algorithm.

Result array has length m + n = 2 + 2 = 4, initialized to all zeros: [0, 0, 0, 0]. Index 0 is the most significant position.

We iterate i from right to left through num1, and for each i, iterate j from right to left through num2. For each pair, p1 = i+j (carry position), p2 = i+j+1 (ones position).

Step 1: i=1 (digit '2'), j=1 (digit '4'). p1=2, p2=3. mul=2×4=8. sum=8+result[3]=8. result[3]=8, carry=0. Result: [0,0,0,8].

Step 2: i=1 (digit '2'), j=0 (digit '3'). p1=1, p2=2. mul=2×3=6. sum=6+result[2]=6. result[2]=6, carry=0. Result: [0,0,6,8].

Step 3: i=0 (digit '1'), j=1 (digit '4'). p1=1, p2=2. mul=1×4=4. sum=4+result[2]=4+6=10. result[2]=10%10=0, carry=10/10=1 → result[1]+=1. Result: [0,1,0,8].

Step 4: i=0 (digit '1'), j=0 (digit '3'). p1=0, p2=1. mul=1×3=3. sum=3+result[1]=3+1=4. result[1]=4, carry=0. Result: [0,4,0,8].

Step 5: Convert result array [0,4,0,8] to string, skip leading zero → "408".

Result: 12 × 34 = 408 ✓. We used only 4 single-digit multiplications — O(m×n).

Grade School Multiplication — 12 × 34 — Watch how each digit-by-digit multiplication places its result at the correct position in the product array, with carries propagating naturally.

Algorithm

  1. If either num1 or num2 is "0", return "0".
  2. Create a result array of length m + n, initialized to all zeros.
  3. Iterate i from m-1 down to 0 (digits of num1 from right to left):
    • For each i, iterate j from n-1 down to 0 (digits of num2 from right to left):
      • Compute mul = digit(num1[i]) × digit(num2[j]).
      • Compute positions: p1 = i + j, p2 = i + j + 1.
      • Compute sum = mul + result[p2].
      • Set result[p2] = sum % 10.
      • Add carry: result[p1] += sum / 10.
  4. Convert the result array to a string, skipping any leading zeros.
  5. Return the result string.

Code

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        if (num1 == "0" || num2 == "0") return "0";
        
        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 p1 = i + j;
                int p2 = i + j + 1;
                int sum = mul + result[p2];
                
                result[p2] = sum % 10;
                result[p1] += sum / 10;
            }
        }
        
        string str;
        for (int digit : result) {
            if (!(str.empty() && digit == 0)) {
                str += to_string(digit);
            }
        }
        
        return str.empty() ? "0" : str;
    }
};
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)
        
        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'))
                p1 = i + j
                p2 = i + j + 1
                total = mul + result[p2]
                
                result[p2] = total % 10
                result[p1] += total // 10
        
        # Convert to string, skip leading zeros
        result_str = ''.join(str(d) for d in result)
        return result_str.lstrip('0') or '0'
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        if (num1.equals("0") || num2.equals("0")) return "0";
        
        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 p1 = i + j;
                int p2 = i + j + 1;
                int sum = mul + result[p2];
                
                result[p2] = sum % 10;
                result[p1] += sum / 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 Analysis

Time Complexity: O(m × n)

We have two nested loops: the outer loop iterates through all m digits of num1, and the inner loop iterates through all n digits of num2. Each iteration performs O(1) work (one multiplication, one addition, one modulo, one division). The final string construction is O(m + n). Total: O(m × n).

With m, n ≤ 200, this is at most 40,000 operations — extremely fast.

Space Complexity: O(m + n)

We allocate a result array of size m + n to hold the digits of the product. The product of an m-digit number and an n-digit number has at most m + n digits (for example, 99 × 99 = 9801 has 4 = 2 + 2 digits). The output string also takes O(m + n) space. Total extra space: O(m + n).