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.
1def multiply(num1: str, num2: str) -> str:
2 if num1 == '0' or num2 == '0':
3 return '0'
4
5 result = [0] * (len(num1) + len(num2))
6
7 for i in range(len(num1) - 1, -1, -1):
8 for j in range(len(num2) - 1, -1, -1):
9 mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
10 p1, p2 = i + j, i + j + 1
11
12 summation = mul + result[p2]
13 result[p2] = summation % 10
14 result[p1] += summation // 10
15
16 result_str = ''.join(map(str, result))
17 return result_str.lstrip('0')This Python solution uses an array (list) to store the intermediate results of each single-digit multiplication. We iterate backwards over both numbers, calculate the multiplication of individual digits, and manage the carry for each step. The results are stored from the least significant to the most significant position.
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.
1def multiply_numbers(num1: str, num2: str)
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.
Optimized through direct multiplication with preexisting carries within the innermost loop, this approach does not drastically alter the foundational logics compared to approach one, yet reduces redundancy in carry handling.