Multiply Strings

NeetCode: Multiply Strings · LeetCode: 43. Multiply Strings · Difficulty: Medium

Given two non-negative integers num1 and num2 as decimal strings, return their product as a string. Do not convert the whole strings to integers and do not use BigInteger.

Example

Text

Input:  num1 = "2",   num2 = "3"      Output: "6"
Input:  num1 = "123", num2 = "456"    Output: "56088"
Input:  num1 = "0",   num2 = "999"    Output: "0"

Brute force: school method with intermediate strings

Multiply as on paper. For each digit of num2 (from the right), multiply the whole num1 by that digit to get a partial product string, append as many zeros as the digit's position, and add all partial products with a string-addition helper. Each partial product and each running sum is a new string, so the method allocates and copies heavily.

A digit character converts to its value with c - '0', and a value converts back with (char) ('0' + v).

Java

class Solution {
    private String addStrings(String a, String b) {
        StringBuilder out = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0) {
            int x = i >= 0 ? a.charAt(i--) - '0' : 0;
            int y = j >= 0 ? b.charAt(j--) - '0' : 0;
            int sum = x + y + carry;
            out.append((char) ('0' + sum % 10));
            carry = sum / 10;
        }
        if (carry > 0) {
            out.append((char) ('0' + carry));
        }
        return out.reverse().toString();
    }

    private String multiplyByDigit(String num, int digit) {
        StringBuilder out = new StringBuilder();
        int carry = 0;
        for (int i = num.length() - 1; i >= 0; i--) {
            int prod = (num.charAt(i) - '0') * digit + carry;
            out.append((char) ('0' + prod % 10));
            carry = prod / 10;
        }
        if (carry > 0) {
            out.append((char) ('0' + carry));
        }
        return out.reverse().toString();
    }

    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        String total = "0";
        int shift = 0;
        for (int i = num2.length() - 1; i >= 0; i--, shift++) {
            String partial = multiplyByDigit(num1, num2.charAt(i) - '0') + "0".repeat(shift);
            total = addStrings(total, partial);
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.multiply("2", "3"));
        System.out.println(s.multiply("123", "456"));
        System.out.println(s.multiply("0", "999"));
        System.out.println(s.multiply("99", "99"));
    }
}

Output

Time: O(n · (m + n)) for lengths m and n, since each of the n partial products is added into a running sum of up to m + n digits. Space: O(m + n) per string, with many temporary strings created along the way.

Optimal: accumulate into a digit-position array

The product of an m-digit and an n-digit number has at most m + n digits, so make pos = new int[m + n].

Position rule: digit a[i] times digit b[j] (both indexed from the left) has a ones part that lands at pos[i + j + 1] and a carry that lands at pos[i + j]. With a[i] worth 10^(m-1-i) and b[j] worth 10^(n-1-j), the product is worth 10^(m+n-2-i-j), which is the place value of index i + j + 1 in an array of length m + n; the carry is one place higher, at i + j.

For each pair, sum = a[i] * b[j] + pos[i + j + 1], then pos[i + j + 1] = sum % 10 and pos[i + j] += sum / 10. A slot may briefly exceed 9 after receiving a carry, but it is normalised when it is visited later as some pair's i + j + 1 slot; pos[0] only receives carries and ends up at most 9. Finally skip leading zeros.

Example "12" * "34" (pos has 4 slots), pairs in the order the loops visit them:

Text

i=1,j=1: 2*4=8      pos = [0,0,0,8]
i=1,j=0: 2*3=6+0    pos = [0,0,6,8]
i=0,j=1: 1*4=4+6=10 pos = [0,0,0,8] then carry: [0,1,0,8]
i=0,j=0: 1*3=3+1=4  pos = [0,4,0,8]   -> "408"

Java

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int sum = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + pos[i + j + 1];
                pos[i + j + 1] = sum % 10;
                pos[i + j] += sum / 10;
            }
        }
        StringBuilder out = new StringBuilder();
        for (int d : pos) {
            if (out.length() == 0 && d == 0) continue; // skip leading zeros
            out.append((char) ('0' + d));
        }
        return out.length() == 0 ? "0" : out.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.multiply("2", "3"));
        System.out.println(s.multiply("123", "456"));
        System.out.println(s.multiply("0", "999"));
        System.out.println(s.multiply("99", "99"));
        System.out.println(s.multiply("12", "34"));
    }
}

Output

Time: O(m * n). Space: O(m + n), only the result array.

Both approaches are quadratic; the digit-position array has a smaller constant and creates no intermediate strings.

How to explain it in an interview

Baseline: multiply num1 by each digit of num2, shift, and add the partial products as strings: O(n * (m + n)) with many temporary strings.
Key insight: digit i times digit j only affects positions i + j and i + j + 1 of an m + n array, so the products can be accumulated directly.
Steps: (1) allocate pos of length m + n; (2) double loop from the right: sum = a[i]*b[j] + pos[i+j+1], ones digit to i+j+1, carry added to i+j; (3) skip leading zeros; (4) return "0" if nothing is left.
Complexity: O(m * n) time, O(m + n) space.
Pitfalls: leading zeros and the "0" input. int cannot overflow here: one step is at most 81 plus the current slot value, and slot values stay small because each slot is reduced below 10 whenever it is the ones slot. Faster multiplication (Karatsuba) exists but is not needed here.