Description:
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.
Examples:
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"Solution in Python:
To solve the problem of multiplying two non-negative integers represented as strings without using built-in BigInteger libraries or converting the strings to integers directly, we can simulate the manual multiplication process.
Python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# If either number is "0", the result is "0"
if num1 == "0" or num2 == "0":
return "0"
# Initialize a result list of zeros with the maximum possible length
# The maximum length of the product will be len(num1) + len(num2)
result = [0] * (len(num1) + len(num2))
# Reverse both strings to make it easier to handle the carry
num1 = num1[::-1]
num2 = num2[::-1]
# Multiply each digit of num1 with each digit of num2
for i in range(len(num1)):
for j in range(len(num2)):
# Multiply the current digits
product = int(num1[i]) * int(num2[j])
# Add the product to the corresponding index in the result list
result[i + j] += product
# Handle the carry
result[i + j + 1] += result[i + j] // 10
result[i + j] %= 10
# Convert the result list to a string
# Remove leading zeros by converting to string and reversing back
result_str = ''.join(map(str, result[::-1])).lstrip('0')
return result_strDetailed Explanation:
- Initialization:
- Check if either
num1ornum2is “0”. If so, return “0” immediately since any number multiplied by 0 is 0. - Initialize a result list of zeros with the length
len(num1) + len(num2). This length is sufficient to hold the product of the two numbers.
- Check if either
- Reversing Strings:
- Reverse both
num1andnum2strings to facilitate the manual multiplication from right to left, similar to how we do multiplication by hand.
- Reverse both
- Multiplication:
- Iterate over each digit of
num1andnum2using nested loops. - Multiply each digit of
num1by each digit ofnum2and add the result to the corresponding index in the result list. - Handle the carry by dividing the current position by 10 and adding the quotient to the next position.
- Iterate over each digit of
- Convert Result List to String:
- Convert the result list to a string. Since the list is in reverse order, reverse it back and use
lstrip('0')to remove any leading zeros.
- Convert the result list to a string. Since the list is in reverse order, reverse it back and use
- Return the Result:
- Return the final result as a string.
This approach ensures that we handle the multiplication process manually, respecting the constraints of not using any built-in BigInteger libraries or converting the inputs to integers directly.
Solution in Javascript:
JavaScript
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function(num1, num2) {
// If either number is "0", the result is "0"
if (num1 === "0" || num2 === "0") {
return "0";
}
// Initialize a result array of zeros with the maximum possible length
// The maximum length of the product will be num1.length + num2.length
let result = new Array(num1.length + num2.length).fill(0);
// Reverse both strings to make it easier to handle the carry
let n1 = num1.split('').reverse();
let n2 = num2.split('').reverse();
// Multiply each digit of num1 with each digit of num2
for (let i = 0; i < n1.length; i++) {
for (let j = 0; j < n2.length; j++) {
// Multiply the current digits
let product = n1[i] * n2[j];
// Add the product to the corresponding index in the result array
result[i + j] += product;
// Handle the carry
if (result[i + j] >= 10) {
result[i + j + 1] += Math.floor(result[i + j] / 10);
result[i + j] %= 10;
}
}
}
// Convert the result array to a string
// Remove leading zeros by converting to string and reversing back
while (result[result.length - 1] === 0) {
result.pop();
}
return result.reverse().join('');
};Solution in Java:
Java
class Solution {
public String multiply(String num1, String num2) {
// If either number is "0", the result is "0"
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
// Initialize a result array of zeros with the maximum possible length
// The maximum length of the product will be num1.length() + num2.length()
int[] result = new int[num1.length() + num2.length()];
// Reverse both strings to make it easier to handle the carry
String n1 = new StringBuilder(num1).reverse().toString();
String n2 = new StringBuilder(num2).reverse().toString();
// Multiply each digit of num1 with each digit of num2
for (int i = 0; i < n1.length(); i++) {
for (int j = 0; j < n2.length(); j++) {
// Multiply the current digits
int product = (n1.charAt(i) - '0') * (n2.charAt(j) - '0');
// Add the product to the corresponding index in the result array
result[i + j] += product;
// Handle the carry
result[i + j + 1] += result[i + j] / 10;
result[i + j] %= 10;
}
}
// Convert the result array to a string
StringBuilder resultStr = new StringBuilder();
for (int i = result.length - 1; i >= 0; i--) {
if (resultStr.length() == 0 && result[i] == 0) {
// Skip leading zeros
continue;
}
resultStr.append(result[i]);
}
return resultStr.toString();
}
}Solution in C#:
C#
public class Solution {
public string Multiply(string num1, string num2) {
// If either number is "0", the result is "0"
if (num1 == "0" || num2 == "0") {
return "0";
}
// Initialize a result array of zeros with the maximum possible length
// The maximum length of the product will be num1.Length + num2.Length
int[] result = new int[num1.Length + num2.Length];
// Reverse both strings to make it easier to handle the carry
char[] n1 = num1.ToCharArray();
char[] n2 = num2.ToCharArray();
Array.Reverse(n1);
Array.Reverse(n2);
// Multiply each digit of num1 with each digit of num2
for (int i = 0; i < n1.Length; i++) {
for (int j = 0; j < n2.Length; j++) {
// Multiply the current digits
int product = (n1[i] - '0') * (n2[j] - '0');
// Add the product to the corresponding index in the result array
result[i + j] += product;
// Handle the carry
result[i + j + 1] += result[i + j] / 10;
result[i + j] %= 10;
}
}
// Convert the result array to a string
StringBuilder resultStr = new StringBuilder();
for (int i = result.Length - 1; i >= 0; i--) {
if (resultStr.Length == 0 && result[i] == 0) {
// Skip leading zeros
continue;
}
resultStr.Append(result[i]);
}
return resultStr.ToString();
}
}