Multiply Two Strings

Posted: 19 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
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.
Try Problem