A festival strings n lanterns in a single line from the entrance gate to the far end. Lantern i starts either lit (1) or unlit (0). The only control available is a single knob: turning it at position i instantly toggles lantern i and every lantern from position i to the far end (each toggled lantern flips lit to unlit or unlit to lit). The knob can be turned at any position, any number of times, in any order. Determine the minimum number of knob turns needed so that every lantern ends up lit at the same time.
Line 1: an integer n.
Line 2: n integers, each 0 or 1 — the initial state of lantern 0..n-1.
A single integer: the minimum number of knob turns required.
1 <= n <= 2*10^50 or 1.Example 1
Input
5 1 0 0 1 0
Expected
3
Explanation
Lantern 0 is already lit, skip it. Lantern 1 is unlit, so turn the knob at position 1: lanterns 1..4 flip, giving [1,1,1,0,1] (1 turn). Lantern 2 is now lit (no turn needed here). Lantern 3 is unlit, so turn the knob at position 3: lanterns 3..4 flip, giving [1,1,1,1,0] (2 turns). Lantern 4 is now unlit, so turn the knob at position 4: it flips to lit, giving [1,1,1,1,1] (3 turns). All lanterns are lit after 3 turns, and fewer turns cannot work since three separate 0-runs had to be corrected.
Example 2
Input
4 1 1 1 1
Expected
0
Explanation
Every lantern is already lit, so no knob turns are needed and the answer is 0.
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 →