Loading page…
Practice problem · easy
At a sorting hub, parcels ride a conveyor belt in a line. Each parcel is bound for van 0 or van 1. Vans pull up to the loading bay one after another, in a fixed order.
The worker at the bay looks at the parcel at the front of the belt. If it is bound for the van at the bay, they load it. If not, they move it to the back of the belt and look at the next one. When no parcel on the belt is bound for the van at the bay, loading stops.
Write parcels_left(parcels, vans).
parcels is the belt from front to back. Each number is 0 or 1, the van that parcel is bound for.vans is the order in which vans reach the bay. It has the same length as parcels.Input: parcels = [1, 1, 0, 0], vans = [0, 1, 0, 1]
Output: 0| Step | Van | Belt before (front first) | What happens | Belt after |
|---|---|---|---|---|
| 1 | 0 |
1 1 0 0 |
the front is 1: rotate it to the back; again; the front is 0: load it |
0 1 1 |
| 2 | 1 |
0 1 1 |
the front is 0: rotate it; the front is 1: load it |
1 0 |
| 3 | 0 |
1 0 |
rotate 1; the front is 0: load it |
1 |
| 4 | 1 |
1 |
the front is 1: load it |
empty |
Every van finds a parcel, so the belt ends up empty.
Input: parcels = [1, 1, 1, 0, 0], vans = [0, 0, 0, 1, 1]
Output: 3The first van needs a 0, and two exist, so two vans load. The third van needs a 0, but none is left, so loading stops with three 1 parcels on the belt.
Input: parcels = [0], vans = [1]
Output: 1No parcel is bound for van 1, so nothing loads.
1 ≤ length of parcels ≤ 10^5vans has the same length as parcelsparcels and vans is 0 or 1A plan that moves parcels one by one can rotate the whole belt for every van. That costs up to n steps for each of n vans: 10^10 for the largest input, which is too slow.
So look for something that rotating never changes. A rotation moves a parcel but never creates or removes one. The numbers of 0 and 1 parcels change only when a parcel is loaded.
parcels_left · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.