716. Gathering the Ones on a Ring

The array of 0 and 1 is arranged in a CIRCLE, so the last position is adjacent to the first. One swap exchanges any two positions. Print the fewest swaps needed to bring every 1 into one contiguous block AROUND THE RING.

1 0 1 0 1 -> 1 1 1 0 0 1 -> 0 the block is positions 3, 4, 0 ... reading around 0 1 0 1 1 -> 1 1 1 1 -> 0

## The only change from problem 700

700 is this question on a straight line. There the destination block is one of n - m + 1 windows; here it is one of n windows, because the block may wrap around the end.

1 1 0 0 1 is the pair worth holding on to: on a line it costs 1 swap, on a ring it costs 0, because positions 4, 0 and 1 are already contiguous around the circle.

## Wrapping without copying the array

The usual trick is to concatenate the array with itself and slide over 2n positions. It works and it doubles the memory.

Reading with a modulus costs nothing and stays in place:

m = number of ones cur = ones in a[0 .. m-1] best = cur for i in 1 .. n-1: cur += a[(i + m - 1) mod n] - a[i - 1] best = max(best, cur) answer = m - best

The window starting at i gains the position m - 1 steps ahead of it and loses the one it just left behind. Both are found with one modulus.

## Why the cost is still m minus the best

Unchanged from 700: a window of length m holding t ones is missing m - t, and the ones outside pair exactly with the zeros inside, so each missing one costs one swap.

## The two cases where the loop must not run

m = 0: no ones, nothing to gather, answer 0, and a window of length 0 cannot be built.

m = n: every position is a one, the block is the whole ring, answer 0. Here the loop would actually still be correct, but stopping early makes the pair of degenerate cases read together rather than one being silently lucky.

## Cost

Time O(n). Space O(1).

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