Multiply Strings
Understanding the Problem
We're given two numbers as strings, and we need to multiply them and return the result as a string. We can't convert them to integers, because the numbers can be up to 200 digits long. That's far beyond what a 64-bit integer (or even a 128-bit one) can hold.
So the task is to simulate multiplication by hand. To multiply 123 by 456, you multiply 123 by each digit of 456, shift the partial results by position, and add them up. That is what we need to implement with strings.
A useful property falls out of that hand method: when you multiply digit i of num1 by digit j of num2, the single-digit product contributes to positions i + j and i + j + 1 of the result array (counting from the left). This positional relationship is what the optimal approach builds on.
Key Constraints:
1 <= num1.length, num2.length <= 200→ The product of an n-digit and an m-digit number has at most n + m digits, so the result needs at most 400 positions. Any O(n m) approach is fine since 200 200 = 40,000 digit multiplications.num1 and num2 consist of digits only→ No negative numbers, decimal points, or invalid characters to handle.No leading zeroes except for "0" itself→ Input is clean, but the output must also strip leading zeroes.
Approach 1: Grade-School Multiplication with Partial Strings
Intuition
This simulates how we multiply on paper directly. Take each digit of num2, multiply it by the entire num1, and accumulate the partial products. Each partial product is shifted left by one more position (appending trailing zeroes) as we move to higher digits of num2.
For example, 123 * 456:
- 123 * 6 = 738
- 123 * 5 = 615, shifted left by 1 = 6150
- 123 * 4 = 492, shifted left by 2 = 49200
- Sum: 738 + 6150 + 49200 = 56088
The work is in two helpers: single-digit multiplication of num1 with carry propagation, and string addition of two partial products. Both are mechanical but verbose.
Algorithm
- Handle the edge case: if either number is
"0", return"0". - For each digit
dinnum2(from right to left): - Multiply the entire
num1byd, propagating carries, to get a partial product string. - Append the appropriate number of trailing zeroes based on
d's position. - Add all partial product strings together using a string addition helper.
- Return the final sum string.
Example Walkthrough
Code
- Time Complexity: O(n * m). For each of the m digits in num2, we multiply it with all n digits of num1. Then we add m partial product strings, where each addition takes O(n + m) time.
- Space Complexity: O(n + m). Each partial product string is at most O(n + m) characters long, and the result string grows to at most O(n + m) characters.
This approach is correct but creates one intermediate string per digit of num2 and runs the carry logic once for every partial-product addition. The next approach accumulates every digit-by-digit product into a single integer array and resolves all carries in one final pass.
Approach 2: Direct Position Multiplication (Optimal)
Intuition
Each pair of digits contributes to a fixed position in the result, so we can skip the intermediate strings entirely. Multiplying digit at index i of num1 (counting from the left) by digit at index j of num2 gives a one- or two-digit product that belongs at positions i + j and i + j + 1 of the result array.
Why i + j and i + j + 1? The digit at index i of num1 represents a value in the 10^(n1-1-i) place, and the digit at index j of num2 represents the 10^(n2-1-j) place. Their product occupies the 10^(n1+n2-2-i-j) place. In a result array of length n1 + n2, that maps to index i + j + 1 for the ones digit and i + j for the tens digit of the single-digit product.
So instead of building partial product strings and adding them, we accumulate each digit-by-digit product directly into the right positions of a result array, letting values grow past 9 for the moment. Once every pair is processed, we sweep carries from right to left and convert the array to a string.
Consider num1 = "123" and num2 = "456". The digit 3 (at index 2 of num1) represents 3 10^0 = 3. The digit 5 (at index 1 of num2) represents 5 10^1 = 50. Their product is 150, which contributes to the 10^1 place (the 5 in 150) and the 10^2 place (the 1 in 150).
In the result array of size 6, position 5 is the ones place, position 4 is the tens place, and so on. Index i + j + 1 = 2 + 1 + 1 = 4 is the tens place, and the carry feeds index i + j = 3, the hundreds place. The same correspondence holds for every digit pair, so accumulating raw products and resolving carries at the end produces the correct number.
Algorithm
- Create an integer array
productsof sizenum1.length + num2.length, initialized to 0. - Iterate through each digit
iofnum1and each digitjofnum2(both from right to left). - Compute the product of
num1[i]andnum2[j]. - Add this product to
products[i + j + 1]. Note: we let values accumulate beyond 9 for now. - After all multiplications, process carries from right to left: for each position, the carry is
products[k] / 10, which gets added toproducts[k - 1], andproducts[k]becomesproducts[k] % 10. - Convert the array to a string, skipping leading zeroes.
Example Walkthrough
Code
- Time Complexity: O(n * m). We iterate through every pair of digits: n digits in num1 times m digits in num2. The carry processing is O(n + m), which doesn't change the overall complexity.
- Space Complexity: O(n + m). The products array has size n + m, and the result string is at most n + m characters long.