Multiply Strings

Moderate
0/80
Average time to solve is 35m
54 upvotes
Asked in companies
SnapdealGoogleFacebook

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
17281 
91276
123
456
Sample Output 1:
1577340556
56088    
Explanation for sample 1:
For the first test case:
A=17281, and B=91276
The product of both numbers is 1577340556.

For the second test case:
A=123, B=456
The product of both numbers is 56088
Sample Input 2:
1
5
10
Sample output 2:
50
Hint

Think of a solution to find the product of both numbers recursively.

Approaches (2)
Recursive Approach

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.
Time Complexity

O(N * M), where N is the length of the string B and M is the length of string A.

 

In the worst case, we will be traversing the complete string A for every digit of string B. Hence the overall Time Complexity will be O(N * M).

Space Complexity

O(N * M), where N is the length of the string B and M is the length of string A.

 

In the worst case, the recursion depth will be N and each recursion state will return a string of length M.Hence the, overall Space Complexity will be O(N * M).

Code Solution
(100% EXP penalty)
Multiply Strings
Full screen
Console