1366. Add Them Up Under a Modulus
Add n integers together and print the total reduced modulo m. The answer
must be the least non-negative value, so it lies in 0 to m-1 and never
carries a minus sign.
n = 5, m = 7 values 1 2 3 4 5 total 15 15 mod 7 -> 1
n = 3, m = 5 values -1 -1 -1 total -3 answer -> 2
## What most people try first
Add every value into one accumulator and reduce once at the end. It is the obvious reading of the question and it breaks on the second test above and on the sixth.
Two separate things go wrong. The total can be far larger than any single
value: 200000 values of 10^9 reach 2 * 10^14, so a 32-bit accumulator is
nowhere near wide enough. And when the total is negative, % does not return
what the question asks for.
## Reduce after every addition
Keep the accumulator already reduced, so it is always in 0 to m-1:
acc = 0
for each value v:
r = v mod m then, if r is negative, r = r + m
acc = acc + r
if acc >= m: acc = acc - m
One subtraction replaces the second %, because acc and r are both below
m, so their sum is below 2m and at most one subtraction is ever needed.
## Why the two agree
Reduction commutes with addition: (x + y) mod m equals
((x mod m) + (y mod m)) mod m. So reducing early can never change the final
residue, because every intermediate value differs from the exact total only by
a multiple of m, and a multiple of m is invisible modulo m.
## The remainder that comes back negative
In C, C++ and Java, % takes the sign of the left operand, so -1 % 7 is
-1, not 6. Python floors instead and gives 6. JavaScript matches C. The
answer this problem wants is the Python one, so the C-family languages need the
explicit fix if (r < 0) r += m. Writing the fix costs nothing in Python and
keeps all five references identical in shape.
## Overflow
Nothing here needs 64 bits once the reduction is done eagerly. The largest
value the loop ever holds is acc + r, with both below m and m at most
10^9, so it tops out at 2 * 10^9, which FITS in a signed 32-bit integer
because the limit is 2147483647. It is the version that adds first and reduces
last that overflows, and that is the whole lesson.
## Cost
O(n) time and O(1) extra space.
Constraints - `1 ≤ n ≤ 200000` - `2 ≤ m ≤ 1000000000` - `-1000000000 ≤ each value ≤ 1000000000`
Input
The first line contains two integers n and m.
The second line contains n integers, the values to add.
Output
Print one integer, the total of the values reduced modulo m, given as the least non-negative residue in the range 0 to m-1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.