670. Swapping Neighbours to Separate the Balls

A row of balls is given as a string of 0 for black and 1 for white. One move swaps two ADJACENT balls.

Print the fewest moves needed to get every black ball before every white one.

101 -> 1 100 -> 2 0111 -> 0 already separated

## Count what each black ball must cross

A black ball ends up before every white ball. Adjacent swaps move it one place at a time, so moving one black ball past one white ball costs exactly one move.

So the total is, over all black balls, the number of white balls currently to their LEFT.

ones = 0, moves = 0 for each character: '1' -> ones += 1 '0' -> moves += ones

One pass, with a running count acting as the trailing pointer.

## Why the blacks never need to cross each other

Their relative order among themselves does not matter, so there is never a reason to swap two blacks, and likewise two whites. Every useful move swaps a black with a white, and each such pair needs exactly one.

So the count above is not merely an upper bound; it is exactly the number of black-white pairs that are currently in the wrong order, and every one of them must be fixed by its own move.

That is an inversion count, and recognising it as one is what makes the linear formula obvious rather than lucky.

## Why a nested loop is too slow

Counting the whites before each black directly is O(n^2), which at 200000 characters is 4 * 10^10. The running count turns it into one pass.

## Overflow

With 100000 whites followed by 100000 blacks the answer is 10^10, well past a signed 32 bit integer. That is exactly the worst case, and it is the one to size the accumulator for.

## Boundaries

A string of one character needs no moves. An already separated string answers 0.

## Cost

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

Constraints - `1 ≤ length ≤ 200000` - the string contains only `0` and `1`