Sum of Two Arrays
You are given two numbers 'A' and 'B' in the form of two arrays (A[] and B[]) of lengths 'N' and 'M' respectively, where each array element represents a digit. You need to find the sum of these two numbers and return this sum in the form of an array.

Note:

1. The length of each array is greater than zero. 2. The first index of each array is the most significant digit of the number. For example, if the array A[] = {4, 5, 1}, then the integer represented by this array is 451 and array B[] = {3, 4, 5} so the sum will be 451 + 345 = 796. So you need to return {7, 9, 6}. 3. Both numbers do not have any leading zeros in them. And subsequently, the sum should not contain any leading zeros.

Input Format:

The first line of the input contains an integer T, denoting the number of test cases. The first line of each test case contains two space-separated integers 'N' and 'M', denoting the size of the two arrays. The second line of each test case contains 'N' space-separated integers denoting the elements of the first array. The third line of each test case contains 'M' space-separated integers denoting the elements of the second array.

Output Format:

The only line of output of each test case contains space-separated digits which correspond to the sum of the two numbers 'A' and 'B'.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Sum of Two Arrays

You are given two numbers 'A' and 'B' in the form of two arrays (A[] and B[]) of lengths 'N' and 'M' respectively, where each array element represents a digit. You need to find the sum of these two numbers and return this sum in the form of an array.

Note:

1. The length of each array is greater than zero.

2. The first index of each array is the most significant digit of the number. For example, if the array A[] = {4, 5, 1}, then the integer represented by this array is 451 and array B[] = {3, 4, 5} so the sum will be 451 + 345 = 796. So you need to return {7, 9, 6}.

3. Both numbers do not have any leading zeros in them. And subsequently, the sum should not contain any leading zeros.

Input Format:

The first line of the input contains an integer T, denoting the number of test cases.

The first line of each test case contains two space-separated integers 'N' and 'M', denoting the size of the two arrays.

The second line of each test case contains 'N' space-separated integers denoting the elements of the first array.

The third line of each test case contains 'M' space-separated integers denoting the elements of the second array.

Output Format:

The only line of output of each test case contains space-separated digits which correspond to the sum of the two numbers 'A' and 'B'.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^2
1 <= N, M <= 10^4
0 <= A[i], B[i] <= 9

Time Limit: 1 sec

Accepted Answer

Two Pointers

Approach 1 would fail if the size of arrays is greater than 18 (as the maximum integer range in most of the programming languages is approximately up to 10^18.), so we need a better way to find the sum.
We will find the sum in the way we generally do it using a pen and paper i.e starting from the right(LSB), adding individual digits and the previous carry.
We can use two pointers to find the sum for each index and keep on storing it in the answer array in the go.
The first thing to note is that we need to traverse both the arrays from the end since we add the numbers from LSB to MSB. So let I = N - 1, J = M - 1 and CARRY = 0.
Let us create array ANS[], which will contain the final answer.
While I >=0 or J >= 0, do the following:
- Initialize SUM = 0 for each iteration, since we want to add the values at current I and J indices only.
- If I >=0 do SUM = SUM + A[I] and I = I - 1.
- If j >=0 do SUM = SUM + B[J] and J = J - 1.
- We need to add the CARRY if it was present from some previous index, so SUM = SUM + carry.
- We have to push the LAST_DIGIT = SUM %10 of the sum into the ANS[].
- Finally do CARRY = SUM /10, because we have already processed the current sum so the CARRY should contain the remaining part.
After the while loop ends, if we have some CARRY left, push it into ANS.
Let us assume that A = [9,9,9] and B = [1,1,1]. After we process arrays for I = 2 and J = 2, we will have :
- SUM = 10, LAST_DIGIT = 10%10 = 0 and CARRY = 1. So we will push 0 in the ANSand our ANS will be [0].
- After 2 more iterations, we will have ANS = [1, 1, 0] and CARRY = 1.
- So after exiting the while loop we will push CARRY into the ANS array and hence our ANS array will be [0, 1, 1, 1].
Now reverse the ANS array and return it.

Space Complexity: O(n)Explanation:

O(1)

In this approach we are using constant extra space.

Time Complexity: O(n)Explanation:

O(max(N, M)), where N is the size of the first array and M is the size of the second array.

As we are iterating till we are not at the end of both the arrays, thus the time complexity will be linear towards the size of the arrays. Hence the time complexity will be O(max(N, M)).