Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Constraints:
1 <= num1.length, num2.length <= 200num1 and num2 consist of digits only.num1 and num2 do not contain any leading zero, except the number 0 itself.The Multiply Strings problem asks you to multiply two non-negative integers represented as strings without converting them directly to built-in numeric types. The key idea is to simulate the grade-school multiplication process digit by digit.
Instead of using integer conversion, iterate through each digit from right to left and multiply pairs of digits. Store intermediate results in a result structure (often an array) sized m + n, where m and n are the lengths of the two strings. Each multiplication contributes to a specific position, and you manage the carry just like manual multiplication.
After processing all digit pairs, handle remaining carries and convert the resulting digits into a final string while removing leading zeros. This simulation-based approach avoids overflow and works efficiently even for very large numbers.
The typical implementation runs in O(m × n) time since every digit pair is multiplied, while the auxiliary storage for the result array requires O(m + n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Digit-by-digit simulation (grade-school multiplication) | O(m × n) | O(m + n) |
NeetCode
This approach mimics the multiplication process that is taught in schools. The idea is to multiply each digit of num1 with each digit of num2 and store the result in the corresponding position in an array. This intermediate result is then summed together to form the final product. We avoid using any built-in library functions for handling large numbers.
Time complexity: O(n * m), where n and m are the lengths of num1 and num2 respectively.
Space complexity: O(n + m) for the result array used to store intermediate results.
1public class Solution {
2 public string Multiply(string num1, string num2) {
3 if (num1 == "0" || num2 == "0") return "0";
4 int n = num1.Length, m = num2.Length;
5 int[] result = new int[n + m];
6
7 for (int i = n - 1; i >= 0; i--) {
8 for (int j = m - 1; j >= 0; j--) {
9 int mul = (num1[i] - '0') * (num2[j] - '0');
10 int sum = mul + result[i + j + 1];
11
12 result[i + j + 1] = sum % 10;
13 result[i + j] += sum / 10;
}
}
StringBuilder sb = new StringBuilder();
foreach (int r in result) {
if (!(sb.Length == 0 && r == 0)) {
sb.Append(r);
}
}
return sb.ToString();
}
}In C#, the solution utilizes an integer array to store the intermediate results, calculated by the direct multiplication of digits. This solution iterates through each character of the numeric strings, converts them to integers before multiplication, and manages the carries.
This approach leverages string manipulation and direct indexing to carefully manage carries and keep track of the multiplication progression similarly to approach one. The ultimate goal is to achieve better space optimization by minimizing the auxiliary storage.
Time complexity: O(n * m), comparable to previous method.
Space complexity: O(n + m) but implemented to handle carry more elegantly.
1public String multiplyNumbers(String num1, String num2)
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Multiply Strings is a common medium-level interview problem. It tests understanding of string manipulation, simulation techniques, and careful handling of carries during arithmetic operations.
The optimal approach simulates manual multiplication used in grade school. Each digit of one string is multiplied with digits of the other and stored in a result array with proper carry handling. This avoids integer overflow and works efficiently for very large numbers.
The problem typically restricts converting the strings to integers because the numbers may exceed the limits of built-in numeric types. Handling digits as characters ensures the solution works for arbitrarily large numbers.
An integer array or list of size m + n is commonly used to store intermediate multiplication results. It allows direct placement of digits based on their positional value and simplifies carry propagation.
Adopted string and array manipulations ensure the effective harnessing of Java's StringBuilder while performing similar operations as in Python to handle carries and intermediate multiplications directly.