A maintenance skiff patrols a straight channel lined with n numbered buoys in a row, indexed 0 through n-1. Each buoy i initially holds nums[i] units of collected debris. The skiff may only launch from a buoy that currently holds zero debris, and at launch it commits to one heading: toward increasing indices, or toward decreasing indices.
Every launch is simulated independently, starting fresh from the buoys' original debris amounts. Once launched from buoy curr with a heading, the skiff repeats the following until it drifts outside the channel:
curr has moved outside the range [0, n-1], the patrol ends.curr currently holds zero debris, the skiff glides through: it takes one more step in its current heading (without changing heading) and continues.curr currently holds more than zero debris, the skiff collects exactly one unit from that buoy (decreasing its count by 1), reverses its heading, and then takes one step in the new heading.A launch (starting buoy, starting heading) is a clean sweep if, at the moment the skiff drifts outside the channel, every buoy holds exactly zero debris. Count how many of the possible clean-sweep launches exist.
The first line contains a single integer n. The second line contains n space-separated integers nums[0] ... nums[n-1].
Print a single integer: the number of (starting buoy, starting heading) launches that are clean sweeps.
Example 1
Input
3 0 1 0
Expected
2
Explanation
There are two candidate starting buoys (0 and 2), each with two headings, for 4 launches total. Starting at buoy 0 heading right: it glides onto buoy 1 (debris 1), collects one unit (now 0), reverses to head left, and glides off the left end with every buoy at zero -- a clean sweep. By symmetry, starting at buoy 2 heading left is also a clean sweep. Starting at buoy 0 heading left, or buoy 2 heading right, immediately exits the channel without ever reaching buoy 1, leaving its debris uncollected. So 2 of the 4 launches are clean sweeps.
Example 2
Input
4 0 2 0 1
Expected
1
Explanation
Buoys 0 and 2 start at zero. Launching from buoy 2 heading left: it collects one unit from buoy 1 (2 -> 1), reverses right, glides through buoy 2, collects the unit from buoy 3 (1 -> 0), reverses left, glides through buoy 2 again, collects the last unit from buoy 1 (1 -> 0), reverses right, then glides through buoys 2 and 3 and exits with every buoy at zero -- a clean sweep. Every other launch (buoy 0 in either heading, or buoy 2 heading right) leaves buoy 1 with leftover debris. So the answer is 1.
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 →