A warehouse tracks n consecutive shifts; shift i moved a net integer count of a[i] pallets (negative means more pallets left than arrived). Given a positive integer k, find the length of the longest contiguous stretch of shifts whose net pallet change is divisible by k. If no non-empty stretch has a sum divisible by k, output 0.
Line 1: an integer n.
Line 2: n space-separated integers, the per-shift net changes in order.
Line 3: an integer k.
A single integer: the length of the longest contiguous stretch whose sum is divisible by k (0 if none exists).
Example 1
Input
5 2 1 4 1 3 3
Expected
4
Explanation
The stretch at positions 2..5 (1,4,1,3) sums to 9, which is divisible by 3, and has length 4; no longer stretch qualifies.
Example 2
Input
3 1 2 3 7
Expected
0
Explanation
No non-empty contiguous stretch sums to a multiple of 7, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →