23. Minimum Swaps to Group Ones

Difficulty: medium · Array, Two Pointers

Problem

You are given a binary array of `n` elements. In one swap you may exchange **any two** elements (they need not be adjacent). Find the minimum number of swaps needed to bring all the `1`s together into one contiguous block. If the array contains no `1` at all, print `-1`.

Input

- Line 1: the integer `n`. - Line 2: `n` space-separated values, each `0` or `1`.

Output

Print the minimum number of swaps, or `-1` if there are no `1`s.

Example 1

Input:
7
1 0 1 0 1 0 0
Output:
1

Explanation: There are three 1s. The window 1 0 1 holds two of them, so one swap (moving the third 1 into the 0) groups them.

Example 2

Input:
5
1 0 1 0 1
Output:
1

Explanation: Every window of length 3 contains one 0, so 1 swap is needed.

Example 3

Input:
3
0 0 0
Output:
-1

Explanation: There are no 1s to group, so the answer is -1.

Constraints

- 1 <= n <= 10^5 - Each value is 0 or 1

Solutions are judged against 3 sample and 9 hidden tests. Sign in to solve it · All problems