Parcels on a conveyor weigh loads[0], loads[1], ... kilograms. Everything that stays on the belt is packed into crates that each hold exactly p kilograms, with no crate partly filled, so the total weight left on the belt must be a multiple of p.
You may take off one run of consecutive parcels (possibly an empty run, meaning you take nothing), but you may not take off every parcel. Return the length of the shortest run that makes the remaining total a multiple of p. Return 0 if nothing needs to be removed, and -1 if no allowed run works.
Examples
Input: loads = [6, 3, 5, 2], p = 9
Output: 2
Explanation: the total is 16. No single parcel leaves a multiple of 9, but removing [5, 2] leaves 9.
Input: loads = [5, 5], p = 3
Output: -1
Explanation: removing one parcel leaves 5, and removing both is not allowed.
Input: loads = [2, 4], p = 3
Output: 0
Constraints
1 <= len(loads) <= 10**51 <= loads[i] <= 10**9,1 <= p <= 10**9- Target complexity: O(n). Trying every run is far too slow for the largest tests.
Goals
- Restate 'what is left is a multiple of p' as a condition on the removed stretch
- Look up the needed prefix remainder in a dictionary
- Keep the latest position of each remainder to make stretches short