Problem of the day
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.
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.
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
2
17281
91276
123
456
1577340556
56088
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
1
5
10
50
Think of a solution to find the product of both numbers recursively.
The idea is to use a recursive approach to multiply two numbers A and B
Steps:
Function to multiply string with a digit :
string multiplyWithDigit(string A, int B):
Function to add two numbers as strings:
string add(string A, string B) :
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).
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).