Subarrays divisible by the shard count

Scenario

A storage service spreads its objects evenly over a number of shards. Each event changes the number of stored objects: an upload adds objects and a cleanup removes them, so a change can be negative.

An operator can absorb a run of consecutive events without rebalancing when the net change of the run is a multiple of the shard count. Net change 0 counts too. You count the runs that can be absorbed.

Your task

Write count_even_runs(changes, shards).

changes[i] is the change in the number of stored objects caused by the i-th event. It can be negative or zero.
A run is one or more consecutive events.
Return the number of runs whose net change is a multiple of shards.
The count can be larger than a 32-bit int, so use a 64-bit result.

Examples

Example 1 (traced)#

text2 lines

Input:  changes = [3, -1, 4, 0, -6, 2], shards = 3
Output: 11

The trace keeps the remainder of the running total, divided by 3, and a table of how often each remainder has occurred. A run ends at the current event for every earlier position with the same remainder. The table starts with remainder 0 once, before any event.

Step	Change	Remainder	Earlier positions with it	Runs so far	Table after
0	start	0		0	0: 1
1	3	0	1	1	0: 2
2	−1	2	0	1	0: 2, 2: 1
3	4	0	2	3	0: 3, 2: 1
4	0	0	3	6	0: 4, 2: 1
5	−6	0	4	10	0: 5, 2: 1
6	2	2	1	11	0: 5, 2: 2

The output is 11.

Example 2#

text2 lines

Input:  changes = [7, -2, 9], shards = 1
Output: 6

With one shard, every net change is a multiple of 1. There are 3 + 2 + 1 = 6 runs.

Example 3#

text2 lines

Input:  changes = [-1, 5], shards = 5
Output: 1

Only the run made of the second event, [5], has a net change that is a multiple of 5. The running total goes from −1 to 4, and both have remainder 4 when divided by 5.

Constraints

0 ≤ changes.length ≤ 100,000 (events in the log)
-10^6 ≤ changes[i] ≤ 10^6 (change caused by one event)
1 ≤ shards ≤ 100,000

What does n ≤ 10^5 tell you?

Trying every start and extending the run one event at a time costs about n × n / 2 steps. For 100,000 events that is about 5 × 10^9, far over the budget of about 10^8 a second. The answer can reach that size too, so it needs 64 bits.

Scenario

A storage service spreads its objects evenly over a number of shards. Each event changes the number of stored objects: an upload adds objects and a cleanup removes them, so a change can be negative.

Your task

Write count_even_runs(changes, shards).

changes[i] is the change in the number of stored objects caused by the i-th event. It can be negative or zero.
A run is one or more consecutive events.
Return the number of runs whose net change is a multiple of shards.
The count can be larger than a 32-bit int, so use a 64-bit result.

Examples

Example 1 (traced)#

text2 lines

Input:  changes = [3, -1, 4, 0, -6, 2], shards = 3
Output: 11

Step	Change	Remainder	Earlier positions with it	Runs so far	Table after
0	start	0		0	0: 1
1	3	0	1	1	0: 2
2	−1	2	0	1	0: 2, 2: 1
3	4	0	2	3	0: 3, 2: 1
4	0	0	3	6	0: 4, 2: 1
5	−6	0	4	10	0: 5, 2: 1
6	2	2	1	11	0: 5, 2: 2

The output is 11.

Example 2#

text2 lines

Input:  changes = [7, -2, 9], shards = 1
Output: 6

With one shard, every net change is a multiple of 1. There are 3 + 2 + 1 = 6 runs.

Example 3#

text2 lines

Input:  changes = [-1, 5], shards = 5
Output: 1

Only the run made of the second event, [5], has a net change that is a multiple of 5. The running total goes from −1 to 4, and both have remainder 4 when divided by 5.

Constraints

0 ≤ changes.length ≤ 100,000 (events in the log)
-10^6 ≤ changes[i] ≤ 10^6 (change caused by one event)
1 ≤ shards ≤ 100,000

What does n ≤ 10^5 tell you?