Multiply Strings
MedPrompt
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 <= 200num1andnum2consist of digits only.- Both
num1andnum2do not contain any leading zero, except the number0itself.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly mimics the way we perform multiplication by hand. We multiply num1 by each digit of num2 one by one, from right to left. Each of these intermediate products is calculated and then added to a running total. To account for the place value of the digit from num2, we pad the intermediate product with trailing zeros.
Algorithm
- Handle the base case where either
num1ornum2is "0". In this case, the product is "0". - Initialize a result string,
totalSum, to "0". - Iterate through the digits of
num2from right to left (from indexn-1down to0). - For each digit
d2innum2: a. Create a helper functionmultiplyByDigitthat takesnum1andd2and returns their product as a string. This function simulates multiplication by iterating throughnum1, multiplying byd2, and handling carries. b. The result frommultiplyByDigitis an intermediate product. Append trailing zeros to this intermediate product based on the position ofd2innum2. For a digit at indexi, appendn-1-izeros. c. Create another helper functionaddStringsthat adds two numbers represented as strings. d. UseaddStringsto add the padded intermediate product tototalSum. - After the loop finishes,
totalSumwill hold the final product.
Walkthrough
The algorithm iterates through num2 from the last digit to the first. In each iteration, we take one digit from num2 and multiply it with the entire num1. This single-digit multiplication is itself a loop, where we iterate through num1, multiply digits, and handle carries. The result is an intermediate product string. We then append a number of zeros to this intermediate product string corresponding to its place value (e.g., for the tens digit, we add one zero; for the hundreds digit, two zeros, and so on). We then implement a separate function to add this padded intermediate product string to our cumulative result string. This process repeats for all digits in num2. The final cumulative result string is the answer.
class Solution { public String multiply(String num1, String num2) { if ("0".equals(num1) || "0".equals(num2)) { return "0"; } String totalSum = "0"; int n = num2.length(); for (int i = n - 1; i >= 0; i--) { int digit2 = num2.charAt(i) - '0'; StringBuilder currentProduct = multiplyByDigit(num1, digit2); // Append zeros for place value for (int j = 0; j < n - 1 - i; j++) { currentProduct.append('0'); } totalSum = addStrings(totalSum, currentProduct.toString()); } return totalSum; } // Helper to multiply a string number by a single digit private StringBuilder multiplyByDigit(String num, int digit) { if (digit == 0) return new StringBuilder("0"); StringBuilder sb = new StringBuilder(); int carry = 0; for (int i = num.length() - 1; i >= 0; i--) { int d1 = num.charAt(i) - '0'; int product = d1 * digit + carry; sb.append(product % 10); carry = product / 10; } if (carry > 0) { sb.append(carry); } return sb.reverse(); } // Helper to add two string numbers private String addStrings(String num1, String num2) { StringBuilder sb = new StringBuilder(); int i = num1.length() - 1, j = num2.length() - 1, carry = 0; while (i >= 0 || j >= 0 || carry > 0) { int d1 = (i >= 0) ? num1.charAt(i--) - '0' : 0; int d2 = (j >= 0) ? num2.charAt(j--) - '0' : 0; int sum = d1 + d2 + carry; sb.append(sum % 10); carry = sum / 10; } return sb.reverse().toString(); }}Complexity
Time
O(n * (m + n))
Space
O(m + n)
Trade-offs
Pros
Conceptually simple and easy to understand as it directly follows the manual method taught in schools.
Cons
Highly inefficient due to the repeated creation and manipulation of strings inside a loop.
The
addStringsoperation becomes progressively slower as thetotalSumstring grows in length.
This approach improves upon the manual simulation by avoiding the creation of intermediate strings and performing additions. Instead, it uses an integer array to store the final result and calculates the contribution of each digit pair's product directly into this array. This is based on the observation that the product of the i-th digit of num1 and the j-th digit of num2 contributes to the (i+j)-th position of the final result.
Algorithm
- Handle the edge case: if
num1ornum2is "0", return "0". - The product of two numbers with lengths
mandncan have at mostm+ndigits. Create an integer arrayresof sizem + nto store the digits of the final product, initialized to zeros. - Iterate
ifromm-1down to0(fornum1). - Inside this loop, iterate
jfromn-1down to0(fornum2). - For each pair of digits
d1 = num1.charAt(i)andd2 = num2.charAt(j): a. Calculate their product:mul = d1 * d2. b. The result of this multiplication contributes to two positions in theresarray. The position for the 'units' digit isp2 = i + j + 1, and the position for the 'tens' (carry) isp1 = i + j. c. Add the product to the existing value atres[p2]:sum = mul + res[p2]. d. The new value atres[p2]is the units digit of this sum:res[p2] = sum % 10. e. The carry is added to the next position:res[p1] += sum / 10. - After the loops complete, the
resarray contains the product's digits. - Convert the
resarray to a string. Iterate through the array, build aStringBuilder, and be sure to skip any leading zeros. If the result is all zeros, return "0".
Walkthrough
We create an integer array, let's call it res, of size m+n to store the digits of the final product. We iterate through num1 and num2 from right to left using nested loops. Let the current indices be i for num1 and j for num2. The product of num1[i] and num2[j] will affect the positions i+j and i+j+1 in our res array. res[i+j+1] stores the "units" part of the product, and res[i+j] stores the "tens" or carry part. For each pair of digits, we calculate their product mul. We add this mul to the value already at res[i+j+1]. The new value at res[i+j+1] becomes (existing_value + mul) % 10. The carry, (existing_value + mul) / 10, is added to res[i+j]. After iterating through all digit pairs, the res array will contain the final product's digits, possibly with leading zeros. Finally, we convert the res array into a string, skipping any leading zeros.
class Solution { public String multiply(String num1, String num2) { if ("0".equals(num1) || "0".equals(num2)) { return "0"; } int m = num1.length(); int n = num2.length(); int[] res = new int[m + n]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int d1 = num1.charAt(i) - '0'; int d2 = num2.charAt(j) - '0'; int mul = d1 * d2; int p1 = i + j; // Position for carry int p2 = i + j + 1; // Position for digit int sum = mul + res[p2]; res[p1] += sum / 10; res[p2] = sum % 10; } } StringBuilder sb = new StringBuilder(); for (int digit : res) { if (!(sb.length() == 0 && digit == 0)) { sb.append(digit); } } return sb.length() == 0 ? "0" : sb.toString(); }}Complexity
Time
O(m * n)
Space
O(m + n)
Trade-offs
Pros
Significantly more efficient than the brute-force approach as it avoids costly intermediate string operations.
This is the standard and optimal solution for typical constraints in coding interviews.
The space and time complexity are optimal for this method of multiplication.
Cons
The logic for placing products into the correct positions in the result array (
i+jandi+j+1) can be slightly tricky to reason about and implement correctly.
Solutions
Solution
public class Solution { public string Multiply(string num1, string num2) { if (num1 == "0" || num2 == "0") { return "0"; } int m = num1.Length; int n = num2.Length; int[] arr = new int[m + n]; for (int i = m - 1; i >= 0; i--) { int a = num1[i] - '0'; for (int j = n - 1; j >= 0; j--) { int b = num2[j] - '0'; arr[i + j + 1] += a * b; } } for (int i = arr.Length - 1; i > 0; i--) { arr[i - 1] += arr[i] / 10; arr[i] %= 10; } int index = 0; while (index < arr.Length && arr[index] == 0) { index++; } StringBuilder ans = new StringBuilder(); for (; index < arr.Length; index++) { ans.Append(arr[index]); } return ans.ToString(); }}class Solution { public String multiply ( String num1 , String num2 ) { if ( "0" . equals ( num1 ) || "0" . equals ( num2 )) { return "0" ; } int m = num1 . length (), n = num2 . length (); int [] arr = new int [ m + n ]; for ( int i = m - 1 ; i >= 0 ; -- i ) { int a = num1 . charAt ( i ) - '0' ; for ( int j = n - 1 ; j >= 0 ; -- j ) { int b = num2 . charAt ( j ) - '0' ; arr [ i + j + 1 ] += a * b ; } } for ( int i = arr . length - 1 ; i > 0 ; -- i ) { arr [ i - 1 ] += arr [ i ] / 10 ; arr [ i ] %= 10 ; } int i = arr [ 0 ] == 0 ? 1 : 0 ; StringBuilder ans = new StringBuilder (); for (; i < arr . length ; ++ i ) { ans . append ( arr [ i ]); } return ans . toString (); } }/** * @param {string} num1 * @param {string} num2 * @return {string} */ var multiply = function (num1, num2) { if (num1 === " 0 " || num2 === " 0 ") return " 0 "; const result = Array(num1.length + num2.length).fill(0); const code_0 = " 0 ".charCodeAt(0); const num1_len = num1.length; const num2_len = num2.length; for (let i = 0; i < num1_len; ++i) { const multiplier_1 = num1.charCodeAt(num1_len - i - 1) - code_0; for (let j = 0; j < num2_len; ++j) { const multiplier_2 = num2.charCodeAt(num2_len - j - 1) - code_0; result[i + j] += multiplier_1 * multiplier_2; } } result.reduce((carry, value, index) => { const sum = carry + value; result[index] = sum % 10; return (sum / 10) | 0; }, 0); return result .slice(0, result.findLastIndex((d) => d !== 0) + 1) .reverse() .join(""); };class Solution { public: string multiply ( string num1 , string num2 ) { if ( num1 == "0" || num2 == "0" ) { return "0" ; } int m = num1 . size (), n = num2 . size (); vector < int > arr ( m + n ); for ( int i = m - 1 ; i >= 0 ; -- i ) { int a = num1 [ i ] - '0' ; for ( int j = n - 1 ; j >= 0 ; -- j ) { int b = num2 [ j ] - '0' ; arr [ i + j + 1 ] += a * b ; } } for ( int i = arr . size () - 1 ; i ; -- i ) { arr [ i - 1 ] += arr [ i ] / 10 ; arr [ i ] %= 10 ; } int i = arr [ 0 ] ? 0 : 1 ; string ans ; for (; i < arr . size (); ++ i ) { ans += '0' + arr [ i ]; } return ans ; } };class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" m, n = len(num1), len(num2) arr = [0] * (m + n) for i in range(m - 1, - 1, - 1): a = int(num1[i]) for j in range(n - 1, - 1, - 1): b = int(num2[j]) arr[i + j + 1] += a * b for i in range(m + n - 1, 0, - 1): arr[i - 1] += arr[i] // 10 arr[i] %= 10 i = 0 if arr[0] else 1 return "" . join(str(x) for x in arr[i:])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.