Last Updated: 25 Nov, 2020
Sum Of Two Arrays
Easy
Asked in companies
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
Approaches
- 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.
Similar problems