The problem
A train picks up and drops off passengers at each station. The list a holds the change at each station: a positive number means people got on, and a negative number means people got off. Return a new list where entry i is the total change up to and including station i.
running_totals([4, 9, 2]) # [4, 13, 15]
running_totals([3, -5, 4, -1]) # [3, -2, 2, 1]
running_totals([]) # []
These totals are called prefix sums. They come back in ARRS-4, where they answer range questions in constant time: the same few steps, however long the list.
Limits
- Up to 200,000 values.
- Return a new list; do not change
a.
Builds on PYTH-2 Loops and comprehensions and PYTH-3 Functions.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Three values | Not run | |
| 2 | Starts the total at zero | Not run | |
| 3 | Negative values | Not run | |
| 4 | One value | Not run | |
| 5 | Empty list | Not run | |
| 6 | The input is not changed | Not run | |
| 7 | 200,000 values | Not run |