Multiply Strings
Problem
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string without using built-in big integer libraries or direct integer conversion.
- 1 ≤ num1.length, num2.length ≤ 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain leading zeros, except the number 0 itself.
Example
num1 = "123", num2 = "456""56088"A brute-force approach would convert the strings to integers and multiply directly, but this is disallowed. Instead, the algorithm simulates the multiplication process digit by digit, similar to how multiplication is done by hand. For example, multiplying '3' by '6' yields 18, which is split into a carry and a remainder. These partial products are accumulated in an array representing the final number in reverse order. After processing all digit pairs, the array is reversed and leading zeros are trimmed to produce the final string result.
Approach
Straightforward Solution
A naive approach would convert the entire strings to integers and multiply, but this is not allowed due to input size and problem constraints.
Core Observation
Multiplying two numbers digit by digit produces partial products that align according to their place values. Each digit multiplication affects two positions in the result array: the current position and the next higher position due to carry-over.
Path to Optimal
The key insight is to simulate the multiplication process manually by reversing the input strings to align least significant digits, multiply each digit pair, accumulate the results in a fixed-size array, and handle carry propagation immediately. This approach avoids integer overflow and respects the string input format.
Optimal Approach
Initialize an array of zeros with length equal to the sum of the input lengths. Reverse both input strings. For each digit in num1, multiply by each digit in num2, add the product to the corresponding position in the result array, and propagate carry to the next position. After processing all pairs, reverse the result array, skip leading zeros, and join the digits into the final string.
Time
O(m * n)
The algorithm performs a nested loop over the digits of num1 and num2, each of length m and n respectively, resulting in O(m * n) multiplications and additions.
Space
O(m + n)
The result array has length m + n to hold the maximum possible number of digits in the product. This auxiliary space is necessary to store intermediate and final results.
Pattern Spotlight
Simulation (Manual Digit-by-Digit Multiplication)
When direct numeric conversion is disallowed, simulate arithmetic operations by processing digits in reverse order, accumulating partial results in an array, and carefully managing carry propagation to build the final result.
Solution
| 1 | class Solution:
|
| 2 | def multiply(self, num1: str, num2: str) -> str:
|
| 3 | if "0" in [num1, num2]:
|
| 4 | return "0"
|
| 5 |
|
| 6 | res = [0] * (len(num1) + len(num2))
|
| 7 | num1, num2 = num1[::-1], num2[::-1]
|
| 8 |
|
| 9 | for i1 in range(len(num1)):
|
| 10 | for i2 in range(len(num2)):
|
| 11 | digit = int(num1[i1]) * int(num2[i2])
|
| 12 | res[i1 + i2] += digit
|
| 13 | res[i1 + i2 + 1] += (res[i1 + i2] // 10)
|
| 14 | res[i1 + i2] = res[i1 + i2] % 10
|
| 15 |
|
| 16 | res, beg = res[::-1], 0
|
| 17 | while beg < len(res) and res[beg] == 0:
|
| 18 | beg += 1
|
| 19 |
|
| 20 | res = map(str, res[beg:])
|
| 21 | return "".join(res) |
Step-by-Step Solution
Handle Zero Edge Case and Initialize Result Array
| 3 | if "0" in [num1, num2]:
|
| 4 | return "0"
|
| 6 | res = [0] * (len(num1) + len(num2))
|
Objective
To quickly return '0' if either input is zero and prepare an array to accumulate digit-wise multiplication results.
Key Insight
If either number is '0', the product is trivially '0', so an early return avoids unnecessary computation. Initializing an array of length equal to the sum of input lengths guarantees enough space to hold the maximum possible digits of the product, preventing overflow and simplifying carry management.
Interview Quick-Check
Core Logic
Early return on zero inputs prevents unnecessary processing and handles a common edge case efficiently.
Core Logic
Allocating a result array of length len(num1) + len(num2) ensures space for the largest possible product.
Common Pitfalls & Bugs
Forgetting to handle the zero input case leads to incorrect results or extra computation.
Reverse Inputs to Align Least Significant Digits
| 7 | num1, num2 = num1[::-1], num2[::-1]
|
Objective
To reverse both input strings so that digit indices correspond to increasing place values, simplifying multiplication and carry handling.
Key Insight
Reversing the strings transforms the problem into a straightforward positional multiplication where index 0 corresponds to the units place, index 1 to tens, and so forth. This eliminates complex index calculations and aligns with the natural way humans perform multiplication by hand.
Interview Quick-Check
Core Logic
Reversing inputs allows direct indexing from least significant digit to most significant digit, simplifying nested loops.
Common Pitfalls & Bugs
Not reversing inputs complicates index calculations and carry propagation.
Multiply Digits and Accumulate Partial Products with Carry Propagation
| 9 | for i1 in range(len(num1)):
|
| 10 | for i2 in range(len(num2)):
|
| 11 | digit = int(num1[i1]) * int(num2[i2])
|
| 12 | res[i1 + i2] += digit
|
| 13 | res[i1 + i2 + 1] += (res[i1 + i2] // 10)
|
| 14 | res[i1 + i2] = res[i1 + i2] % 10
|
Objective
To perform digit-by-digit multiplication, accumulate partial sums in the result array, and propagate carries immediately to maintain correct digit values.
Key Insight
Each digit multiplication affects two adjacent positions in the result array: the current index for the remainder and the next index for the carry. By adding the product to the current position and immediately propagating the carry to the next, the algorithm maintains the invariant that each position holds a single digit (0-9). This simulates manual multiplication and ensures correctness without extra passes.
Interview Quick-Check
Core Logic
Nested loops multiply each digit pair and add the product to the correct position in the result array, handling carry immediately.
State & Boundaries
Carry is propagated to the next higher digit position to maintain single-digit values in each array slot.
Common Pitfalls & Bugs
Failing to propagate carry immediately leads to incorrect digit values and requires additional passes.
Complexity
This step dominates the time complexity at O(m * n), where m and n are input lengths.
Finalize Result by Removing Leading Zeros and Constructing Output String
| 16 | res, beg = res[::-1], 0
|
| 17 | while beg < len(res) and res[beg] == 0:
|
| 18 | beg += 1
|
| 20 | res = map(str, res[beg:])
|
| 21 | return "".join(res) |
Objective
To reverse the accumulated result array back to normal order, skip leading zeros, and convert digits to a string for the final output.
Key Insight
After multiplication and carry propagation, the result array is in reverse order with possible leading zeros. Reversing it restores the correct digit order. Skipping leading zeros ensures the output does not have unnecessary padding. Converting digits to strings and joining them produces the final product string as required.
Interview Quick-Check
Core Logic
Reversing the result array restores the correct digit order from most significant to least significant.
State & Boundaries
Leading zeros are skipped to avoid incorrect representation of the number.
Common Pitfalls & Bugs
Failing to remove leading zeros can cause incorrect output like '000123'.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if "0" in [num1, num2]:Check if either input string is '0' and return '0' immediately.
This early exit handles the trivial multiplication case where the product is zero, avoiding unnecessary computation and ensuring correctness for zero inputs.
res[i1 + i2 + 1] += (res[i1 + i2] // 10)Add carry-over to the next position in the result array.
Propagating carry immediately ensures each position holds a single digit, maintaining the correctness of the intermediate state and avoiding extra passes.
return "0"Return the string '0' for zero input case.
Returning here terminates the function early, providing the correct product for zero inputs without further processing.
res = [0] * (len(num1) + len(num2))Initialize a result array of zeros with length equal to sum of input lengths.
Allocating this fixed-size array ensures enough space to hold the maximum possible digits of the product, simplifying accumulation and carry management.
res[i1 + i2] += digitAdd the product to the current position in the result array.
Accumulating the product at the correct index aggregates partial sums from all digit pairs contributing to that place value.
res[i1 + i2] = res[i1 + i2] % 10Reduce the current position to a single digit by modulo 10.
This step finalizes the digit at the current position after carry propagation, ensuring the array represents valid digits.
beg += 1Increment the index while the current digit is zero to skip leading zeros.
This loop ensures that all leading zeros are bypassed, preventing incorrect output like '000123'.
num1, num2 = num1[::-1], num2[::-1]Reverse both input strings to align digits from least significant to most significant.
Reversing inputs allows direct indexing from units place upwards, simplifying nested loops and carry propagation logic.
digit = int(num1[i1]) * int(num2[i2])Calculate the product of the current digits from num1 and num2.
This multiplication produces the partial product that contributes to the final result at a specific digit position.
res, beg = res[::-1], 0Reverse the result array to restore normal digit order.
Reversing the array converts it from least significant digit first back to most significant digit first, preparing for output formatting.
while beg < len(res) and res[beg] == 0:Initialize an index to skip leading zeros in the result array.
Leading zeros do not contribute to the numeric value and must be skipped to produce a correct string representation.
return "".join(res)Join the string digits into the final product string and return it.
Joining the digits produces the final string representation of the product, completing the algorithm.
for i1 in range(len(num1)):Iterate over each digit index in reversed num1.
This outer loop selects each digit of num1 for multiplication, establishing the first dimension of the digit-by-digit product.
for i2 in range(len(num2)):Iterate over each digit index in reversed num2.
This inner loop selects each digit of num2 to multiply with the current digit of num1, completing the pairwise multiplication.
res = map(str, res[beg:])Convert the remaining digits to strings for joining.
Mapping digits to strings prepares them for concatenation into the final output string.
Test Your Understanding
Why is it necessary to reverse the input strings and accumulate results in a fixed-size array rather than directly building the result string?
Reversing the strings aligns the least significant digits for straightforward positional multiplication and accumulation. Using a fixed-size array allows efficient carry propagation and avoids repeated string concatenations, which are costly. This approach simulates manual multiplication digit by digit, ensuring correctness without converting the entire input to integers.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Multiply Strings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Multiply Strings drill