# Multiply Two Strings

Posted: 19 Dec, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note:

``````There are no leading zeros in both the strings, except the number 0 itself.
Do not use any built-in Big Integer Library.
``````
##### For Example:
``````If, A = 123, and B = 456.
So the product of both numbers will be 56088.
``````
##### Input format:
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains a number ‘A’ as a string.
The second line of each test case contains the number ‘B’ as a string.
``````
##### Output format:
``````For each test case, print the product of both the numbers, ‘A’ and ‘B’ in a separate line.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= |A|, |B| <= 100

where |A| and |B| denote the length of string, ‘A’ and ‘B’ respectively.
All the characters of the string ‘A’ and ‘B’ contain digits only.

Time limit: 1 second
`````` Approach 1

The idea is to use a recursive approach to multiply two numbers A and B

Steps:

1. If any of the numbers is 0 then we return 0 as an answer.
2. Then we multiply the rightmost digit of number B with A i.e Define and call a helper function multiplyWithDigit(A, P), to calculate the product of digit P with A, where A is the given number and P is the rightmost digit of B.
3. Now If the length of B>1, In this case,  we will recursively call for the number excluding the rightmost digit of B.
4. In the end, we will return the addition of 10 times the result of a recursive function and the result obtained in step 2.

Function to multiply string with a digit :

string multiplyWithDigit(string A, int B):

1. Initialize carry to  0 and an empty string to store the result say answer.
2. Traverse the string A from right to left and on each iteration extract the digit from the string A to multiply it with the digit B and add carry to it and store the result as P. Add P%10 to our answer string and update carry as P/10
3. In the end, if a non-zero carry exists add it to the answer string.
4. At last, reverse the answer string and then return it.

Function to add two numbers as strings:

string add(string A, string B) :

1. Swap A with B if the length of B is smaller than the length of A.
2. Initialize a variable carry to  0 and an empty string to store the result say answer.
3. Traverse the string A from right to left and on each iteration extract the digit from the string A then do:
1. Add extracted digit with the corresponding digit of string B and also add carry to it then store the result as P.
2. Now add P%10 to our answer string and update carry as P/10
4. When string A is traversed and some characters of string B  remain then assume zeros in string A at those places and will do similar operations as mentioned above.
5. In the end, if a non-zero carry exists add it to the answer string.
6. Reverse the answer string and return it.