Running sum

Easy

2000 ms limit256 MB memoryArrays Prefix sums

Stuck?

Show a hint

Keep one number as you walk the list: the total so far. Each answer is that total plus the current value.

The ideas behind this problem

How a solution runs here Arrays and lists in everyday code Where your data actually lives Arrays: what is cheap and what is not Carrying an answer forward: Kadane's algorithm Loops with for, while and do while Arrays, and allocating memory Loops Vectors and the standard algorithms Loops Arrays and ArrayList Loops with for and while Lists and tuples

Next in this lesson

How many digits

Given a list of numbers, return a list where each position holds the sum of every number up to and including that position.

This is called a running sum, or a prefix sum.

Worked example#

For [1, 2, 3, 4]:

position	numbers so far	running sum
0	1	1
1	1, 2	3
2	1, 2, 3	6
3	1, 2, 3, 4	10

So the answer is [1, 3, 6, 10].

Notice that each answer is the previous answer plus the current number. You do not need to add up everything again at each step, which is what makes this fast.

Constraints#

1 <= n <= 100000
-1000 <= nums[i] <= 1000

Input

nums is a count then that many integers.

Output

The running sums, separated by spaces.

Examples

Input

4
1 2 3 4

Output

1 3 6 10

1, then 1+2=3, then 3+3=6, then 6+4=10.

Input

5
1 1 1 1 1

Output

1 2 3 4 5

Adding one each time, so the running sum counts up.

Input

3
3 -1 -2

Output

3 2 0

Negative numbers bring the running total back down.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.