Gather the Ones

Medium

The array bits holds only zeros and ones. In one swap you may exchange any two elements of the array, not necessarily neighbours. Find the smallest number of swaps after which all the ones sit next to each other in a single unbroken block. Where that block ends up does not matter. If there are no ones, or they are already together, the answer is 0.

Example 1

bits=[0, 1, 1, 0, 0, 1, 0] → 1

There are three ones. Swapping bits[3] and bits[5] gives [0, 1, 1, 1, 0, 0, 0], so one swap is enough.

Example 2

bits=[1, 0, 0, 1, 0, 0, 1, 1] → 2

The best spot for the four ones is the last four cells: two ones are already there, and two swaps bring in the other two.

Example 3

bits=[0, 0, 0] → 0

Constraints

1 ≤ len(bits) ≤ 10⁵
Each bits[i] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Sliding Window

Similar problems

Shortest Stretch to the Goal Medium Evenly Stepped Stretches Medium Longest Run of Ones With One Fix Medium Nearest k Values Medium Windows With a Small Product Medium

Input

bits=[0, 1, 1, 0, 0, 1, 0]

Expected

Run checks the first 3 tests in your browser. Submit checks all 120 tests on the server, hidden ones included.