707. Fewest Length-k Flips to Make Everything One

One move picks k CONSECUTIVE positions in a 0/1 array and flips all of them. Print the fewest moves that make every value 1, or -1 if it cannot be done.

0 1 0, k = 1 -> 2 0 0 0 1 0 1 1 0, k = 3 -> 3 1 1 1, k = 2 -> 0 1 1 0, k = 2 -> -1

## Two facts that make it greedy

Order does not matter. Flipping is its own inverse and the moves commute, so a solution is just a SET of starting positions.

Flipping the same position twice is wasted. So each start is used at most once, and the answer is how many starts are chosen.

Now sweep left to right. Position 0 can only be fixed by a move starting at 0, so if a[0] is 0 that move is forced. Once it is made, position 1 is in the same situation, and so on.

There is no choice anywhere, which is what makes a greedy sweep correct rather than merely plausible: at every step exactly one move can still repair the current position.

## The window of active flips

Recounting how many flips currently cover position i is O(n * k). Instead carry one bit, the PARITY of the flips covering i, and a small array recording where each flip stops:

cur = 0 for i in 0 .. n-1: cur ^= ends[i] # a flip started at i-k stops covering i if (a[i] ^ cur) == 0: # still zero after the flips in force if i + k > n: return -1 # no room for a move starting here moves += 1 cur ^= 1 ends[i + k] ^= 1

cur is the running parity, ends marks where a flip leaves the window, and the two XORs are the whole bookkeeping. This is a difference array over XOR rather than addition.

## Why the failure test is i + k > n

A move starting at i needs k positions, so it exists only while i + k <= n. When a zero is found past that point nothing can repair it and the answer is -1.

1 1 0 with k = 2 fails exactly there: the zero is at index 2, and 2 + 2 > 3.

## Boundaries

k = 1 answers the number of zeros. An array already all ones answers 0 whatever k is.

## Cost

Time O(n). Space O(n) for the end markers.

Constraints - `1 ≤ k ≤ n ≤ 200000` - each value is `0` or `1`