Loading...
Loading...
Loading...
A bank account changes by a signed amount each day. Count the blocks of consecutive days whose changes add up to exactly zero. Blocks at different positions count separately, even when they hold the same numbers.
Example
Input
5 1 -1 2 -2 3
Output
3
The blocks are (1, -1), (2, -2) and (1, -1, 2, -2): 3 blocks.
Try the problem first. Open one hint at a time.
Adding up every block is O(n^2). Think of running totals: if two running totals are equal, the block between them adds up to zero.
Keep a dictionary of how many times each running total has appeared. Start with total 0 seen once.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor