All problems

Leftover Parcel Run

Medium · prefix sum

A warehouse sends parcels down a belt, in order. The list weights holds the weight of each parcel in kilograms.

Parcels are packed into crates that each hold exactly crate kilograms. If you take a run of neighbouring parcels, with none skipped, and pack their total weight into as many full crates as you can, some weight is left over. That leftover is the total weight divided by crate, taking the remainder. For example, a run weighing 9 kilograms with crate = 4 fills two crates and leaves 1.

Return the number of parcels in the longest run whose leftover is exactly leftover. If no run leaves exactly that amount, return 0.

Examples

Example 1

Input: weights = [3, 5, 4, 2], crate = 4, leftover = 1

Output: 2

The run 5, 4 weighs 9, which is two full crates and 1 left over. No run of three or four parcels leaves 1.

Example 2

Input: weights = [2, 3, 4, 1], crate = 5, leftover = 0

Output: 4

All four parcels weigh 10, exactly two full crates with nothing left over.

Example 3

Input: weights = [4, 4], crate = 4, leftover = 3

Output: 0

Every run weighs 4 or 8, which always leaves 0.

Constraints