Last Updated: 19 Dec, 2020
Multiply Strings
Moderate
Asked in companies
You are given two big numbers ‘A’ and ‘B’ as strings. Your task is to find the product of both the numbers.
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
Approaches
The idea is to use a recursive approach to multiply two numbers A and B
Steps:
- If any of the numbers is 0 then we return 0 as an answer.
- 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.
- Now If the length of B>1, In this case, we will recursively call for the number excluding the rightmost digit of B.
- 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):
- Initialize carry to 0 and an empty string to store the result say answer.
- 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
- In the end, if a non-zero carry exists add it to the answer string.
- At last, reverse the answer string and then return it.
Function to add two numbers as strings:
string add(string A, string B) :
- Swap A with B if the length of B is smaller than the length of A.
- Initialize a variable carry to 0 and an empty string to store the result say answer.
- Traverse the string A from right to left and on each iteration extract the digit from the string A then do:
- Add extracted digit with the corresponding digit of string B and also add carry to it then store the result as P.
- Now add P%10 to our answer string and update carry as P/10
- 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.
- In the end, if a non-zero carry exists add it to the answer string.
- Reverse the answer string and return it.
The idea is to use the basic multiplication approach that is taught in elementary school.
The approach is similar to the first approach, just that we will be doing it in an iterative manner.
Steps:
- Create a result vector of length equal to the sum of the length of both the strings and initialise each element of the result vector to 0.
- Traverse string A from the right and multiply each digit of A with the string B and shift the result iteration count by 1 time to the right.
- Add the result obtained in step 2 to the result vector by adding both the numbers digit by digit.
- In the end, convert the result vector into a string and trim leading zeros from it and return the result in reversed order.