Loading
Loading
A shipping company records the daily change in its container count — positive when containers arrive, negative when they leave. Containers are loaded onto trains of a fixed capacity, so a stretch of consecutive days is tidy when its net change is an exact multiple of that capacity.
Return how many non-empty contiguous stretches of values have a total divisible by k. A total of 0 counts, and negative multiples count.
values = [3, 1, 2, -2, 5], k = 3prefix totals 0, 3, 4, 6, 4, 9start with the empty prefixremainders 0, 0, 1, 0, 1, 0two prefixes with equal remainder bound a divisible stretchfour 0s → 6 pairs, two 1s → 1 pair6 + 1 = 7 stretches7Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n + k) time · O(k) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Seven stretches: [3], [3, 1, 2], the whole list, [1, 2], [1, 2, -2, 5], [2, -2] and [-2, 5]. Each totals 0, 3, 6 or 9.
Example 2
Only the whole stretch, totalling 0, works — and 0 is a multiple of every k.