Sweaty Imposter

Multiply Strings

MediumMath & GeometryNeetCode 150MidOpen on LeetCodeUpdated

You're given two non-negative integers num1 and num2 as decimal strings. Return their product, also as a decimal string. Each number can be up to 200 digits long, so don't convert the inputs to built-in integers or use a big-integer library.

Examples

num1 = "12", num2 = "34" returns "408"

The digit products 2 * 4, 2 * 3, 1 * 4, and 1 * 3 land in the ones, tens, tens, and hundreds places: 8 + 100 + 300 = 408.

num1 = "507", num2 = "46" returns "23322"

507 * 46 = 23322. Carries move left one place at a time as each digit product is added in.

num1 = "981", num2 = "0" returns "0"

A zero product is the single digit 0, with no leading zeros.

Constraints

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 contain only digits.
  • Neither number has leading zeros, except the number 0 itself.

Hints

Hint 1

How many digits can the product of an m-digit number and an n-digit number have?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Do grade-school multiplication into one array for the whole result. The product of an m-digit and an n-digit number has at most m + n digits, so allocate pos of length m + n. Counting indices from the left, the product of num1[i] and num2[j] belongs at position i + j + 1, and its carry belongs at i + j. Loop i and j from the right: add the digit product to pos[i + j + 1], keep the ones digit there, and add the rest into pos[i + j]. Finally skip leading zeros and join the digits, returning "0" when nothing is left. O(m * n) time and O(m + n) space.

Time

O(m * n)

Space

O(m + n)

Pitfall

Getting the positions wrong. Indices i and j count from the left, so their product lands at i + j + 1 with the carry at i + j. A fixed result array of length m + n avoids shifting and adding partial products by hand.

Solutions

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] += sum / 10;
                pos[i + j + 1] = sum % 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int d : pos) {
            if (sb.length() == 0 && d == 0) continue;
            sb.append(d);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}
Drill This