Last Updated: 1 Dec, 2021
Complete Sum
Easy
Asked in company
Ninja has an array ‘A’ of size ‘N’. He recently created a topic ‘Complete Sum’ and defined the term ‘completeSum[i]’ = Sum ( A[0] … A[i] ).
Output the complete sum array of array ‘A’.
Example :
N = 3
A = [ 1, 2, 3 ]
Explanation :
Complete sum for index 0 is ‘A[0]=1’.
Complete sum for index 1 is ‘A[0] + A[1]’ = 3.
Complete sum for index 2 is ‘A[0] + A[1] + A[2]’ = 6.
So, we output [ 1, 3, 6 ].
Input Format :
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.
The second line of each test case contains an integer ‘N’ denoting the size of array ‘A’.
The third line of each test case contains ‘N’ space-separated integers denoting the elements of array ‘A’.
Output format :
For each test case, print the complete sum array for array ‘A’.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 10^5
0 <= A[i] <= 10^4
Time Limit : 1 sec
Approaches
Approach :
- As the problem statement suggests, for each index ‘i’, we find the sum of all elements from ‘A[0]’ to ‘A[i]’ of array ‘A’.
Algorithm :
- Initialise a 1-D array ‘res’ of size ‘N’.
- Run a for loop from ‘i=0’ to ‘i=N-1’ :
- Initialise a variable ‘sum’ = 0.
- Run a for loop from ‘j=0’ to ‘j=i-1’ :
- Add to ‘sum’ the value of ‘A[j]’.
- Update ‘res[i] = sum’.
- Return ‘res’ as the final array.
Approach :
- Let us establish a relationship between ‘completeSum[i]’ and ‘completeSum[i-1]’.
- ‘completeSum[i-1]’ = ‘sum( A[0] … A[i-1] )’.
- ‘completeSum[i]’ = ‘sum( A[0] … A[i] )’.
- ‘completeSum[i]’ = ‘sum( A[0] … A[i-1] )’ + ‘A[i]’.
- ‘completeSum[i]’ = ‘completeSum[i-1]’ + ‘A[i]’.
- So, we can calculate ‘completeSum[i]’ using ‘completeSum[i-1]’.
- Hence, we just use the above relation to find the final array optimally.
Algorithm :
- Initialise a 1-D array ‘res’ of size ‘N’.
- Assign ‘res[0]’ as ‘A[0]’.
- Run a for loop from ‘i=1’ to ‘i=N-1’ :
- Assign ‘res[i]’ as ‘res[i-1]’ + ‘A[i]’.
- Return ‘res’ as the final array.
Similar problems