315. Longest Stretch Divisible by K
Print the length of the longest contiguous stretch whose sum is divisible by
k. Print 0 if there is none.
Prefix sums again, with one change: what matters is not the running total but
its REMAINDER when divided by k. A stretch is divisible by k exactly when
the remainder is the same at both of its ends.
So keep a map from remainder to the earliest index. There are only k possible
remainders, so an array of size k replaces the map entirely.
Negative values need care. In most languages -1 % 3 is -1 rather than
2, and the two must be treated as the same remainder or the map splits them
apart and misses matches.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 100000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the length of the longest stretch whose sum is divisible by k, or 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.