Multiply Strings

Multiply Strings is the big sibling of Add Strings. The same trap is here. You cannot just convert to numbers, because the numbers can be huge. So you multiply them by hand, like you did in school. This one trips people up because of where each digit lands. Get the position right and the rest is easy.

🎯 The Problem

You get two numbers as strings and return their product as a string. The whole trick is position, where each digit pair lands in the answer.

The rules:

• The inputs are non-negative numbers given as strings.
• You may not convert the whole string to an integer.
• You multiply digit by digit, like you did in school.
• Digit i of the first number times digit j of the second lands at slots i + j and i + j + 1.

Input:  num1 = "12", num2 = "24"
Output: "288"

Explanation:
    1 2
  x 2 4
  -----
    4 8   (12 x 4)
  2 4     (12 x 20)
  -----
  2 8 8

The product of two numbers with m and n digits has at most m + n digits. So we make an answer array of that size and fill it.

Here is the position rule. Each pair of digits from the two numbers feeds two slots in the result array.

🐢 Approach 1: Convert And Multiply (Brute Force)

The idea in one line: turn both strings into numbers, multiply, then turn the result back to a string.

The idea:

• Call int(num1) * int(num2).
• Convert the product back into a string.

How it works:

• The language parses each string into an integer.
• The built-in multiply does the work.

Why it is weak:

• The product of two long numbers is even longer.
• In C, C++, and Java it overflows. Overflow means the value grew past what the type can store, so it wraps to a wrong number.
• Python handles big integers fine, but the interviewer wants the manual method.

Here is the conversion code for that idea:

def multiply(num1, num2):
    return str(int(num1) * int(num2))

⚡ Approach 2: Grade-School With A Position Grid (Best)

The idea in one line: multiply digit by digit and drop each product into fixed slots of an answer array.

The idea:

• Make an answer array of size m + n, filled with zeros.
• Multiply each digit of num1 by each digit of num2.
• Each digit pair feeds two fixed slots.

How it works:

• For the pair at indices i and j, the product is 0 to 81.
• Slot p2 = i + j + 1 holds the low place. Slot p1 = i + j holds the carry place.
• Add the product to whatever sits at p2. The last digit stays at p2. The rest carries up to p1.
• Read the array left to right and skip leading zeros. If everything is zero, return "0".

Why it is fast:

• The position rule means each product always lands at i + j and i + j + 1.
• Two nested loops touch each digit pair once, so time is O(m times n).
• It never converts the whole string, so it works for any length.

Steps to Solve

1. If either string is "0", the answer is "0". Handle that first.
2. Make an answer array of size m + n, all zeros.
3. Loop i over num1 from the last digit to the first.
4. Inside, loop j over num2 from the last digit to the first.
5. Multiply the two digits. Add the product to the value already at position i + j + 1.
6. The digit kept at i + j + 1 is that sum modulo ten. The carry added to position i + j is the sum divided by ten.
7. After both loops, read the array left to right, skip leading zeros, and join into a string.

Here is the answer array for "12" times "24". Each digit pair drops into its slot, and the carries settle to give 288.

#include <stdio.h>
#include <string.h>

void multiply(const char *num1, const char *num2, char *out) {
    int m = (int)strlen(num1);
    int n = (int)strlen(num2);
    if (strcmp(num1, "0") == 0 || strcmp(num2, "0") == 0) {
        out[0] = '0';
        out[1] = '\0';
        return;
    }

    int pos[256] = {0};  // answer slots, size m + n is enough
    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;        // carry slot
            int p2 = i + j + 1;    // low slot
            int sum = mul + pos[p2];
            pos[p2] = sum % 10;    // keep last digit
            pos[p1] += sum / 10;   // push carry left
        }
    }

    int k = 0;
    int start = 0;
    while (start < m + n - 1 && pos[start] == 0) start++;  // skip leading zeros
    for (int p = start; p < m + n; p++) {
        out[k++] = (char)('0' + pos[p]);
    }
    out[k] = '\0';
}

int main(void) {
    char out[300];
    multiply("12", "24", out);
    printf("%s\n", out);
    return 0;
}

288

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

string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    int m = (int)num1.size();
    int n = (int)num2.size();
    vector<int> pos(m + n, 0);  // answer slots

    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;        // carry slot
            int p2 = i + j + 1;    // low slot
            int sum = mul + pos[p2];
            pos[p2] = sum % 10;    // keep last digit
            pos[p1] += sum / 10;   // push carry left
        }
    }

    string result;
    for (int p = 0; p < m + n; p++) {
        if (!(result.empty() && pos[p] == 0)) {  // skip leading zeros
            result += (char)('0' + pos[p]);
        }
    }
    return result.empty() ? "0" : result;
}

int main() {
    cout << multiply("12", "24") << endl;
    return 0;
}

288

public class MultiplyStrings {
    public static String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int m = num1.length();
        int n = num2.length();
        int[] pos = new int[m + n];  // answer slots

        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;        // carry slot
                int p2 = i + j + 1;    // low slot
                int sum = mul + pos[p2];
                pos[p2] = sum % 10;    // keep last digit
                pos[p1] += sum / 10;   // push carry left
            }
        }

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

    public static void main(String[] args) {
        System.out.println(multiply("12", "24"));
    }
}

288

def multiply(num1, num2):
    if num1 == "0" or num2 == "0":
        return "0"
    m, n = len(num1), len(num2)
    pos = [0] * (m + n)             # answer slots

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48)
            p1, p2 = i + j, i + j + 1   # carry slot, low slot
            total = mul + pos[p2]
            pos[p2] = total % 10        # keep last digit
            pos[p1] += total // 10      # push carry left

    result = "".join(str(d) for d in pos).lstrip("0")  # drop leading zeros
    return result if result else "0"


print(multiply("12", "24"))

288

function multiply(num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";
  const m = num1.length;
  const n = num2.length;
  const pos = new Array(m + n).fill(0); // answer slots

  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const mul = (num1.charCodeAt(i) - 48) * (num2.charCodeAt(j) - 48);
      const p1 = i + j; // carry slot
      const p2 = i + j + 1; // low slot
      const sum = mul + pos[p2];
      pos[p2] = sum % 10; // keep last digit
      pos[p1] += Math.floor(sum / 10); // push carry left
    }
  }

  const result = pos.join("").replace(/^0+/, ""); // drop leading zeros
  return result === "" ? "0" : result;
}

console.log(multiply("12", "24"));

288

Let us read the Python version line by line. First we check for "0". If either input is zero, the product is "0", so we return early. This avoids a messy answer full of zeros.

Then pos = [0] * (m + n) makes the answer array. Two numbers with m and n digits multiply into at most m + n digits, so this size always fits. Every slot starts at zero.

The outer loop runs i from the last digit of num1 back to the first. The inner loop runs j from the last digit of num2 back to the first. So every digit of the first number meets every digit of the second.

Inside, mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48) is the product of the two single digits. The ord(...) - 48 turns a character like '7' into the number 7. Then p1, p2 = i + j, i + j + 1 are the two slots this product touches. We add mul to whatever is already at p2. The last digit of that sum stays at p2. The rest carries to p1 with +=, because that slot may already hold a value from an earlier pair.

At the end we join all slots into one string and call lstrip("0") to remove leading zeros. If everything was stripped, we fall back to "0".

⏱️ Time and Space Complexity

We have two nested loops, one over each string. So the time is O(m times n), where m and n are the two lengths. The answer array has size m + n, so the space is O(m + n). There is a faster method using Fast Fourier Transform for very large numbers, but it is far more complex and almost never expected in an interview.

🧩 Key Takeaways

• ✅ The product of two numbers with m and n digits has at most m + n digits, so size your array that way.
• ✅ Digit i times digit j lands at slots i + j and i + j + 1 of the answer.
• ✅ Add the product into the low slot, keep the last digit, and carry the rest left.
• ✅ Handle the zero case first, or you get a string of zeros instead of “0”.
• ✅ Skip leading zeros when you read the array into the final string.

🚀 What’s Next?

• Add Strings
• Decode String