Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Constraints:
- The length of both num1 and num2 is less than 110.
- Both num1 and num2 contain only digits 0-9.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
Examples:
Input: num1 = "123", num2 = "456"
Output: "56088"
Explanation: 123 * 456 = 56088
Input: num1 = "0", num2 = "0"
Output: "0"
Explanation: 0 * 0 = 0
Solutions
Grade School Multiplication
Time: O(m*n)Space: O(m+n)
This solution uses the grade school multiplication method, where each digit of one number is multiplied by each digit of the other number, and the results are added together.
function multiply(num1, num2) {
let result = 0;
for (let i = num1.length - 1; i >= 0; i--) {
for (let j = num2.length - 1; j >= 0; j--) {
const mul =
(num1.charCodeAt(i) - '0'.charCodeAt(0)) *
(num2.charCodeAt(j) - '0'.charCodeAt(0));
result += mul * Math.pow(10, num1.length - 1 - i + (num2.length - 1 - j));
}
}
return result.toString();
}
Follow-up:
How would you optimize this solution for very large inputs?
