String-based multiplication

You are twenty minutes into a Bloomberg phone screen when the interviewer asks, "How would you multiply two very large numbers that don't fit into a 64-bit integer?" You pause. The numbers are given as strings, and you cannot use any BigInteger library. This problem, also known as Multiply Strings on other platforms, strips away the convenience of built-in arithmetic and asks you to implement multiplication from scratch. It is a favorite at companies like Amazon, Google, Meta, and Bloomberg because it tests whether you can translate a familiar pencil-and-paper process into clean, working code.

TL;DR

Simulate grade-school multiplication using an integer array of size m + n (where m and n are the lengths of the two input strings). For every pair of digits num1[i] and num2[j], multiply them and add the product to result[i + j + 1]. Propagate the carry to result[i + j]. After processing all pairs, convert the array to a string while skipping leading zeros. This runs in O(m * n) time and O(m + n) space.

Why This Problem Matters

String-based multiplication sits at the intersection of simulation, math, and string manipulation. It forces you to think about positional arithmetic, carry propagation, and index mapping. These skills transfer directly to problems involving big number addition, polynomial multiplication, and even FFT-based algorithms used in competitive programming. If you can implement this cleanly, you demonstrate the kind of low-level reasoning that interviewers at Amazon, Two Sigma, and Google value.

Understanding the Problem

Let's be precise about what we need to do:

Given: Two non-negative integers num1 and num2, represented as strings Return: Their product, also as a string Constraints: No built-in BigInteger, no direct conversion to integers

multiply("2", "3")     => "6"
multiply("123", "456") => "56088"
multiply("0", "123")   => "0"

The input strings can have up to 200 digits each. That means the numbers can be astronomically large, well beyond the range of any primitive integer type.

Edge Cases to Consider

1. Either input is "0": The product is always "0". Handle this upfront.
2. Single-digit inputs: The simplest case, but your algorithm should handle it naturally.
3. Large carry chains: Inputs like "999" * "999" generate carries that propagate across multiple positions.
4. Asymmetric lengths: One number might be much longer than the other.

The Grade-School Approach

Think back to how you learned multiplication in school. To multiply 123 by 45, you would:

1. Multiply 123 by 5 (the ones digit of 45) to get 615
2. Multiply 123 by 4 (the tens digit of 45) to get 492, shifted one position left
3. Add the partial results: 615 + 4920 = 5535

The algorithm we will implement follows the same logic, but instead of working with partial products as separate numbers, we accumulate results directly into a single array. This avoids the need to add multiple intermediate results at the end.

How the Result Array Works

The product of an m-digit number and an n-digit number has at most m + n digits. So we allocate a result array of that size and fill it with zeros.

For each pair of digits num1[i] and num2[j]:

• Their product lands at position i + j + 1 in the result array
• Any carry goes to position i + j

Why i + j + 1? Consider the digit at index i in num1 and index j in num2. The digit at index i represents a value in the (m - 1 - i)-th power of 10, and similarly for j. Their combined power maps to position i + j + 1 in the result array (counting from the left, with the most significant digit at index 0).

Here is a visual showing how digits in "123" map to positions in the result array when multiplied by a single-digit number:

Step-by-Step Walkthrough

Let's trace through multiply("12", "3"):

Setup: m = 2, n = 1, result = [0, 0, 0]

Iteration 1: i = 1, j = 0 (digits '2' and '3')

• mul = 2 * 3 = 6
• sum = 6 + result[2] = 6 + 0 = 6
• result[2] = 6 % 10 = 6
• result[1] += 6 / 10 = 0
• Result: [0, 0, 6]

Iteration 2: i = 0, j = 0 (digits '1' and '3')

• mul = 1 * 3 = 3
• sum = 3 + result[1] = 3 + 0 = 3
• result[1] = 3 % 10 = 3
• result[0] += 3 / 10 = 0
• Result: [0, 3, 6]

Skip the leading zero, and we get "36". Correct.

When Carries Get Interesting

Now let's trace multiply("99", "9") to see carry propagation in action:

Setup: m = 2, n = 1, result = [0, 0, 0]

Iteration 1: i = 1, j = 0 (digits '9' and '9')

• mul = 9 * 9 = 81
• sum = 81 + result[2] = 81
• result[2] = 81 % 10 = 1
• result[1] += 81 / 10 = 8
• Result: [0, 8, 1]

Iteration 2: i = 0, j = 0 (digits '9' and '9')

• mul = 9 * 9 = 81
• sum = 81 + result[1] = 81 + 8 = 89
• result[1] = 89 % 10 = 9
• result[0] += 89 / 10 = 8
• Result: [8, 9, 1]

No leading zeros. The answer is "891".

Notice how the carry from the first iteration (8 at position 1) gets picked up and combined with the product from the second iteration. This is the elegance of accumulating directly into the result array.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public String multiply(String num1, String num2) {
    // Handle the zero case upfront
    if (num1.equals("0") || num2.equals("0")) {
      return "0";
    }

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

    // Multiply each digit pair, accumulating into result array
    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 + result[i + j + 1];

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

    // Build the result string, skipping leading zeros
    StringBuilder sb = new StringBuilder();
    for (int num : result) {
      if (!(sb.length() == 0 && num == 0)) {
        sb.append(num);
      }
    }

    return sb.toString();
  }
}

The entire algorithm breaks down into three clear sections:

1. Zero check: Short-circuit if either input is "0"
2. Digit-pair multiplication: The nested loop that does the real work
3. String construction: Convert the result array to a string, dropping leading zeros

Each section is self-contained and easy to explain in an interview.

Complexity Analysis

Time Complexity: O(m * n)

The nested loop iterates over every pair of digits. For strings of length m and n, that is m * n iterations. Each iteration does constant work: one multiplication, one addition, one modulo, and one division. Converting the result array to a string is O(m + n), which is dominated by the main loop.

Space Complexity: O(m + n)

We allocate a result array of size m + n and a StringBuilder of at most the same size. No additional data structures are needed.

This is optimal. You cannot do better than O(m * n) for the multiplication step because every digit pair must be considered (though asymptotically faster algorithms like Karatsuba exist, they are not expected in interviews).

A Larger Example

Let's see the algorithm in action on multiply("123", "45"):

The result array starts at [0,0,0,0,0]. As each digit pair is processed right to left, the partial products accumulate with carries propagating leftward. After six digit-pair multiplications, the final array holds the digits of 5535.

Common Pitfalls

1. Forgetting the zero check: Without it, your algorithm works but wastes time and could produce an empty string for "0" * "0".

2. Off-by-one in position mapping: The positions i + j and i + j + 1 are specific to 0-indexed strings. Getting these wrong shifts all digits.

3. Not handling leading zeros: The result array will often have a leading zero (e.g., [0, 3, 6] for 12 * 3). Forgetting to skip it means returning "036" instead of "36".

4. Using integer conversion as a shortcut: Converting each character to an integer using library methods that internally parse multi-digit strings defeats the purpose of the problem.

Pro tip: If you are unsure about the position formula, trace through a 2-digit times 1-digit example on paper. It takes 30 seconds and catches index bugs before they reach your code.

Interview Tips

When tackling this problem in a live interview:

1. Start by explaining the approach: "I will simulate grade-school multiplication using an array to accumulate partial products." This immediately tells the interviewer you have a plan.

2. Draw the position mapping: Sketch how digit positions in the inputs correspond to positions in the result array. Interviewers love visual explanations.

3. Handle zero first: It shows attention to edge cases and simplifies the rest of the code.

4. Walk through a small example: Trace "12" * "3" before coding. It validates your approach and catches off-by-one errors.

5. Mention Karatsuba: If the interviewer asks about faster approaches, mention the Karatsuba algorithm at O(n^1.585) and FFT-based multiplication at O(n log n). You do not need to implement them, but knowing they exist shows depth.

Key Takeaways

• The grade-school multiplication algorithm maps directly to code: multiply each digit pair and accumulate at positions i + j + 1 (product) and i + j (carry).
• The result array of size m + n is the key data structure. It eliminates the need to track and add separate partial products.
• Always handle the zero case before entering the main loop. It avoids empty-string bugs and is an easy edge case to explain.
• Right-to-left iteration through both strings ensures that carry propagation flows naturally from the least significant to the most significant digit.
• This problem is mathematically equivalent to polynomial multiplication, which is worth mentioning if the interviewer asks for deeper analysis.

Related Problems and Next Steps

If you found this problem interesting, these related challenges build on similar skills:

• Add two numbers represented as strings (simpler version, good warm-up)
• Add two numbers represented as linked lists (different data structure, same carry logic)
• Pow(x, n) with fast exponentiation (another simulation/math hybrid)

This problem and many others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. Consistent practice with problems like this builds the pattern recognition that makes interview day feel routine rather than stressful.

Solutions in Other Languages

Python

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

        len1, len2 = len(num1), len(num2)
        result = [0] * (len1 + len2)

        for i in range(len1 - 1, -1, -1):
            for j in range(len2 - 1, -1, -1):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                sum_ = mul + result[i + j + 1]

                result[i + j + 1] = sum_ % 10
                result[i + j] += sum_ // 10

        result_str = ''.join(map(str, result)).lstrip('0')
        return result_str if result_str else "0"

JavaScript

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

    const m = num1.length, n = num2.length;
    const result = Array(m + n).fill(0);

    for (let i = m - 1; i >= 0; i--) {
      for (let j = n - 1; j >= 0; j--) {
        const mul = (num1[i] - '0') * (num2[j] - '0');
        const sum = mul + result[i + j + 1];

        result[i + j + 1] = sum % 10;
        result[i + j] += Math.floor(sum / 10);
      }
    }

    while (result[0] === 0) {
      result.shift();
    }

    return result.join('');
  }
}

C++

#include <string>
#include <vector>

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

    int m = num1.size(), n = num2.size();
    std::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 sum = mul + result[i + j + 1];

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

    std::string product;
    for (int num : result) {
      if (!(product.empty() && num == 0)) {
        product.push_back(num + '0');
      }
    }

    return product.empty() ? "0" : product;
  }
};

Go

package solution

func (s *Solution) Multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    m, n := len(num1), len(num2)
    result := make([]int, m+n)

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

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

    var resStr string
    for i := 0; i < len(result); i++ {
        if !(resStr == "" && result[i] == 0) {
            resStr += string(result[i] + '0')
        }
    }

    return resStr
}

Scala

class Solution {
  def multiply(num1: String, num2: String): String = {
    if (num1 == "0" || num2 == "0") return "0"

    val m = num1.length
    val n = num2.length
    val result = Array.fill(m + n)(0)

    for (i <- m - 1 to 0 by -1) {
      for (j <- n - 1 to 0 by -1) {
        val mul = (num1(i) - '0') * (num2(j) - '0')
        val sum = mul + result(i + j + 1)

        result(i + j + 1) = sum % 10
        result(i + j) += sum / 10
      }
    }

    val sb = new StringBuilder
    for (num <- result) {
      if (!(sb.isEmpty && num == 0)) sb.append(num)
    }

    if (sb.isEmpty) "0" else sb.toString()
  }
}

Kotlin

class Solution {
    fun multiply(num1: String, num2: String): String {
        if (num1 == "0" || num2 == "0") {
            return "0"
        }

        val m = num1.length
        val n = num2.length
        val result = IntArray(m + n)

        for (i in m - 1 downTo 0) {
            for (j in n - 1 downTo 0) {
                val mul = (num1[i] - '0') * (num2[j] - '0')
                val sum = mul + result[i + j + 1]

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

        val sb = StringBuilder()
        for (num in result) {
            if (!(sb.isEmpty() && num == 0)) {
                sb.append(num)
            }
        }

        return sb.toString()
    }
}

Ruby

class Solution
  def multiply(num1, num2)
    return "0" if num1 == "0" || num2 == "0"

    m, n = num1.length, num2.length
    result = Array.new(m + n, 0)

    (m - 1).downto(0) do |i|
      (n - 1).downto(0) do |j|
        mul = (num1[i].ord - '0'.ord) * (num2[j].ord - '0'.ord)
        sum = mul + result[i + j + 1]

        result[i + j + 1] = sum % 10
        result[i + j] += sum / 10
      end
    end

    result.drop_while { |d| d == 0 }.join
  end
end

TypeScript

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

    const m = num1.length, n = num2.length;
    const result: number[] = Array(m + n).fill(0);

    for (let i = m - 1; i >= 0; i--) {
      for (let j = n - 1; j >= 0; j--) {
        const mul = Number(num1[i]) * Number(num2[j]);
        const sum = mul + result[i + j + 1];

        result[i + j + 1] = sum % 10;
        result[i + j] += Math.floor(sum / 10);
      }
    }

    while (result[0] === 0) {
      result.shift();
    }

    return result.join('');
  }
}

Rust

impl Solution {
    pub fn multiply(&self, num1: String, num2: String) -> String {
        if num1 == "0" || num2 == "0" {
            return "0".to_string();
        }

        let a = num1.as_bytes();
        let b = num2.as_bytes();
        let m = a.len();
        let n = b.len();
        let mut result = vec![0i32; m + n];

        for i in (0..m).rev() {
            for j in (0..n).rev() {
                let mul = (a[i] - b'0') as i32 * (b[j] - b'0') as i32;
                let sum = mul + result[i + j + 1];

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

        let mut s = String::new();
        for &num in &result {
            if !(s.is_empty() && num == 0) {
                s.push_str(&num.to_string());
            }
        }

        s
    }
}

Swift

class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        if num1 == "0" || num2 == "0" {
            return "0"
        }

        let digits1 = Array(num1)
        let digits2 = Array(num2)
        let m = digits1.count
        let n = digits2.count
        var result = [Int](repeating: 0, count: m + n)

        for i in stride(from: m - 1, through: 0, by: -1) {
            for j in stride(from: n - 1, through: 0, by: -1) {
                let mul = Int(digits1[i].asciiValue! - 48) * Int(digits2[j].asciiValue! - 48)
                let sum = mul + result[i + j + 1]

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

        var product = ""
        for num in result {
            if !(product.isEmpty && num == 0) {
                product += String(num)
            }
        }

        return product
    }
}

C#

using System.Text;

public class Solution {
    public string Multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }

        int m = num1.Length, n = num2.Length;
        var result = new int[m + n];

        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 + result[i + j + 1];

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

        var sb = new StringBuilder();
        foreach (int num in result) {
            if (!(sb.Length == 0 && num == 0)) {
                sb.Append(num);
            }
        }

        return sb.ToString();
    }
}

Dart

class Solution {
  String multiply(String num1, String num2) {
    if (num1 == "0" || num2 == "0") {
      return "0";
    }

    int m = num1.length;
    int n = num2.length;
    List<int> result = List.filled(m + n, 0);

    for (int i = m - 1; i >= 0; i--) {
      for (int j = n - 1; j >= 0; j--) {
        int mul = (num1.codeUnitAt(i) - 48) * (num2.codeUnitAt(j) - 48);
        int sum = mul + result[i + j + 1];

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

    StringBuffer sb = StringBuffer();
    for (int num in result) {
      if (!(sb.isEmpty && num == 0)) {
        sb.write(num);
      }
    }

    return sb.toString();
  }
}

PHP

<?php

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

        $m = strlen($num1);
        $n = strlen($num2);
        $result = array_fill(0, $m + $n, 0);

        for ($i = $m - 1; $i >= 0; $i--) {
            for ($j = $n - 1; $j >= 0; $j--) {
                $mul = (ord($num1[$i]) - ord('0')) * (ord($num2[$j]) - ord('0'));
                $sum = $mul + $result[$i + $j + 1];

                $result[$i + $j + 1] = $sum % 10;
                $result[$i + $j] += intdiv($sum, 10);
            }
        }

        $productStr = '';
        foreach ($result as $digit) {
            if (!($productStr === '' && $digit === 0)) {
                $productStr .= $digit;
            }
        }

        return $productStr;
    }
}