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.