grid47 Exploring patterns and algorithms
Nov 2, 2024
6 min read
Solution to LeetCode 43: Multiply Strings Problem
Given two non-negative integers represented as strings, return their product as a string. You must not use any built-in BigInteger library or convert the inputs to integers directly.
Problem
Approach
Steps
Complexity
Input: You are given two non-negative integers 'num1' and 'num2' represented as strings.
Example: Input: num1 = "3", num2 = "4"
Constraints:
• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.
Output: Return the product of num1 and num2 as a string.
Example: Output: "12"
Constraints:
• The output should be a valid representation of the product as a string.
Goal: The goal is to simulate the multiplication of two numbers represented as strings and return the result as a string.
Steps:
• Initialize an array to hold the product of the two numbers.
• Multiply each digit of num1 with each digit of num2, and store the result in the appropriate position of the array.
• Handle the carry-over values from multiplication and adjust the positions accordingly.
• Convert the array back to a string, ensuring there are no leading zeroes.
Goal: The constraints ensure that the inputs are within the expected range and consist only of digits.
Steps:
• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.
Assumptions:
• Both num1 and num2 are valid non-negative integer strings.
• Input: Input: num1 = "3", num2 = "4"
• Explanation: In this case, the multiplication of 3 and 4 results in 12.
• Input: Input: num1 = "45", num2 = "23"
• Explanation: The result of multiplying 45 and 23 is 1035.
• Input: Input: num1 = "99", num2 = "99"
• Explanation: Multiplying 99 by 99 results in 9801.
Approach: We simulate the multiplication of the two numbers by multiplying each digit of num1 with each digit of num2, and handle the carries appropriately.
Observations:
• We cannot directly convert the strings to integers, so we need to simulate the multiplication process manually.
• This problem can be solved by iterating over the digits of the two strings and performing traditional multiplication, while storing the intermediate results in an array.
Steps:
• Initialize a result array to hold intermediate multiplication results.
• For each digit in num1, multiply it with each digit in num2, and store the result in the correct position in the result array.
• Handle carries by updating adjacent positions in the result array.
• Finally, convert the result array into a string, ensuring no leading zeros are included.
Empty Inputs:
• If either num1 or num2 is '0', return '0' as the result.
Large Inputs:
• For large inputs, ensure that the solution efficiently handles up to 200 digits without exceeding time limits.
Special Values:
• Handle the case where either num1 or num2 is a single digit, or where one of them is zero.
Constraints:
• Ensure the output string represents the correct result without leading zeros, except when the result is zero.
string multiply(string num1, string num2) {
if (num1 =="0"|| num2 =="0") return"0";
vector<int> res(num1.size()+num2.size(), 0);
for (int i = num1.size()-1; i >=0; i--) {
for (int j = num2.size()-1; j >=0; j--) {
res[i + j +1] += (num1[i]-'0') * (num2[j]-'0');
res[i + j] += res[i + j +1] /10;
res[i + j +1] %=10;
}
}
int i =0;
string ans ="";
while (res[i] ==0) i++;
while (i < res.size()) ans += to_string(res[i++]);
return ans;
}
1 : Function Declaration
string multiply(string num1, string num2) {
This line declares a function named `multiply` that takes two strings `num1` and `num2` representing large numbers as input and returns a string representing their product.
2 : Base Case
if (num1 =="0"|| num2 =="0") return"0";
This line handles the base case where either `num1` or `num2` is "0". In this case, the product is "0", so the function returns "0".
3 : Vector Initialization
vector<int> res(num1.size()+num2.size(), 0);
This line initializes a vector `res` of size `num1.size() + num2.size()` to store the intermediate results of the multiplication. It is initialized with zeros.
This nested loop performs the multiplication digit by digit. 1. **Digit-wise Multiplication:** The product of the digits at positions `i` and `j` in `num1` and `num2`, respectively, is added to the corresponding position in the `res` vector. 2. **Carry Handling:** If the sum at a position exceeds 9, the carry-over digit is added to the next higher position in the `res` vector. 3. **Modulo Operation:** The current position in the `res` vector is updated to store only the single-digit remainder after the carry-over.
5 : Result String Construction
int i =0;
string ans ="";
while (res[i] ==0) i++;
while (i < res.size()) ans += to_string(res[i++]);
This part constructs the final result string `ans` from the `res` vector. 1. **Skip Leading Zeros:** The loop skips leading zeros in the `res` vector. 2. **Convert Digits to String:** The remaining digits in `res` are converted to strings and appended to the `ans` string.
6 : Return Result
return ans;
This line returns the final result string `ans`.
Best Case: O(N * M)
Average Case: O(N * M)
Worst Case: O(N * M)
Description: The time complexity is proportional to the product of the lengths of num1 and num2, since we multiply each digit of num1 with each digit of num2.
Best Case: O(N + M)
Worst Case: O(N + M)
Description: The space complexity depends on the size of the result array, which can be at most the sum of the lengths of num1 and num2.
