Complete Sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
41 upvotes
Asked in company
Microsoft

Problem statement

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 ].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
3 1 2
4
1 1 1 1
Sample Output 1 :
3 4 6
1 2 3 4
Explanation Of Sample Input 1 :
For test case 1 we have, 

Complete sum for index 0 is ‘A[0]=3’.

Complete sum for index 1 is ‘A[0] + A[1]’ = 4.

Complete sum for index 2 is ‘A[0] + A[1] + A[2]’ = 6.

So, we output [ 3, 4, 6 ].

For test case 2 we have, 

Complete sum for index 0 is ‘A[0]=1’.

Complete sum for index 1 is ‘A[0] + A[1]’ = 2.

Complete sum for index 2 is ‘A[0] + A[1] + A[2]’ = 3.

Complete sum for index 3 is ‘A[0] + A[1] + A[2] + A[3]’ = 4.


So, we output [ 1, 2, 3, 4 ].
Sample Input 2 :
2
2
7 2 
5
4 1 7 5 1
Sample Output 2 :
7 9
4 5 12 17 18
Hint

 Find the complete sum for each index.

Approaches (2)
Brute Force

 

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.

 

Time Complexity

O(N^2), where ‘N’ is the size of array ‘A’.
 

We are finding the prefix sum of all indexes, so the overall time complexity is O(N^2).

 

Space Complexity

O(1) 

 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

 

Code Solution
(100% EXP penalty)
Complete Sum
Full screen
Console