# Solution For Multiply Strings

Problem Statement:

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = “2”, num2 = “3”
Output: “6”

Example 2:

Input: num1 = “123”, num2 = “456”
Output: “56088”

Note:

The length of both num1 and num2 is < 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.

Solution:

One approach to solve the problem is to simulate the multiplication process we use in our school. The idea is to multiply each digit of the second number (i.e., num2) with each digit of the first number (i.e., num1) and add the results at the appropriate positions to get the final product. We can store the result in a list and then convert it to a string.

Algorithm:
1. Initialize a list res with length (m+n) and fill it with 0’s where m and n are the length of num1 and num2 respectively.
2. Reverse both strings (num1 and num2) to start from the least significant digit.
3. Traverse num1 from right to left and multiply each digit with num2 from right to left. The product will have two digits, and we can keep the least significant digit at the current position and carry the higher digit to the next position.
4. After completing the first multiplication, we will have m+n-1 digits in the result. If there is a carry at the last position, add it to the next position.
5. Repeat the same process for all digits of num1.
6. Remove the leading zeros from the result, and if the result is empty, return “0”.
7. Convert the result list to a string and return it.

Time Complexity: O(m*n), where m and n are the lengths of num1 and num2 respectively, as we need to multiply each digit of num1 with each digit of num2.

Space Complexity: O(m+n), for the result list.

Python Code:

class Solution:
def multiply(self, num1: str, num2: str) -> str:

``````    m, n = len(num1), len(num2)
res = [0]*(m+n)

num1 = num1[::-1]
num2 = num2[::-1]

for i in range(m):
carry = 0
for j in range(n):
prod = int(num1[i])*int(num2[j])
pos = i+j
res[pos] += (prod%10 + carry)
carry = prod//10 + res[pos]//10
res[pos] = res[pos]%10

if carry:
res[i+j+1] += carry

while len(res)>1 and res[-1]==0:
res.pop()

return "".join(map(str, res[::-1])) if res else "0"
``````

## Step by Step Implementation For Multiply Strings

```public class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] pos = new int[m + n];

for(int i = m - 1; i >= 0; i--) {
for(int j = n - 1; j >= 0; j--) {
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int p1 = i + j, p2 = i + j + 1;
int sum = mul + pos[p2];

pos[p1] += sum / 10;
pos[p2] = (sum) % 10;
}
}

StringBuilder sb = new StringBuilder();
for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();
}
}```
```def multiply(num1, num2):

# Base cases
if num1 == "0" or num2 == "0":
return "0"

# num1 and num2 are not zero

# Initialize result
result = [0] * (len(num1) + len(num2))

# Go from right to left in num1
for i in range(len(num1) - 1, -1, -1):

# Go from right to left in num2
for j in range(len(num2) - 1, -1, -1):

# Multiply digits and place them in the correct position
# in the result
result[i + j + 1] += int(num1[i]) * int(num2[j])

# Handle carry
if result[i + j + 1] >= 10:
result[i + j] += result[i + j + 1] // 10
result[i + j + 1] %= 10

# Convert result to string
return "".join(map(str, result))```
```var multiply = function(num1, num2) {
};```
```class Solution {
public:
string multiply(string num1, string num2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len1 = num1.size(), len2 = num2.size();
string res(len1 + len2, '0');
for(int i = len1 - 1; i >= 0; --i) {
int carry = 0;
for(int j = len2 - 1; j >= 0; --j) {
int tmp = (res[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
res[i + j + 1] = tmp % 10 + '0';
carry = tmp / 10;
}
res[i] += carry;
}
size_t startpos = res.find_first_not_of("0");
if(string::npos != startpos) {
return res.substr(startpos);
}
return "0";
}
};```
```public class Solution {
public string Multiply(string num1, string num2) {
// convert strings to arrays of characters for easier manipulation
char[] n1 = num1.ToCharArray();
char[] n2 = num2.ToCharArray();

// create a new array to store the result with an extra element for the carry
int[] result = new int[n1.Length + n2.Length];

// iterate through each digit in num1
for(int i = n1.Length - 1; i >= 0; i--) {
// iterate through each digit in num2
for(int j = n2.Length - 1; j >= 0; j--) {
// multiply the digits and store the result in the appropriate index of the result array
// the appropriate index is calculated by taking the sum of the current indices in num1 and num2 and subtracting it from the end of the result array
result[i + j + 1] += (n1[i] - '0') * (n2[j] - '0');
}
}

// iterate through result array
for(int i = result.Length - 1; i > 0; i--) {
// if the current element is greater than 9, carry the 1
if(result[i] > 9) {
result[i - 1] += result[i] / 10;
result[i] %= 10;
}
}

// convert result array to string
string output = string.Join("", result);