[1] Division into cases based on the number of \(1\)

Let \(k\) be the number of 1 in \(S\).

In each operation, \(k\) increases by \(0\), \(+2\), or \(-2\), so the objective is unachievable if \(k\) is odd. Below, assume that \(k\) is even.

• The case \(k=0\)

Nothing to consider.

• The case \(k\geq 4\)

Let \(x_1,x_2,\ldots,x_k\) be the coins showing heads from left to right. Then, one can achieve the objective in \(\frac{k}{2}\) operations by flipping coins \(1\) and \(x_{\frac{k}{2}+1}\), coins \(2\) and \(x_{\frac{k}{2}+2}\), and so on.

• The case \(k=2\)

If the coins showing heads are not adjacent, the answer is \(1\). Below, assume that they are adjacent, and let \(x\) be the coin to the left.

If \(x\geq 3\), one can achieve the objective in two operations by flipping coins \(1\) and \(x\) and then flipping coins \(1\) and \(y\).

If \(x+1\leq N-2\), one can again achieve the objective in two operations by flipping coins \(1\) and \(N\) and then flipping coins \(x\) and \(y\).

Neither of the above is satisfied if \(x<3\) and \(x+1 > N-2\), which happens only if \(N=3\) or \(4\).

If \(N=3\), then \(S\) is 011 or 110, in which case one can only flip coins \(1\) and \(3\), so the objective is unachievable.

If \(N=4\), \(x<3\), and \(x+1 > N-2\), then \(S\) is 0110, in which case the objective is achievable in three operations (0110\(\to\)1111\(\to\)0101\(\to\)0000). One can show by brute force that it cannot be achieved in two operations.

All these conditions can be checked in \(\mathrm{O}(N)\) time.

---

[2] Sample implementations

C++:

#include <bits/stdc++.h>
using namespace std;

int solve() {
    int n;
    string s;
    cin >> n >> s;
    int one = count(s.begin(), s.end(), '1');
    if(one & 1) return -1;
    bool adj = 0;
    for(int i = 0; i < n - 1; i++)
        if(s[i] == '1' and s[i] == s[i + 1]) adj = 1;
    if(one != 2 or !adj) return one / 2;
    if(n == 3) return -1;
    if(n == 4 and s == "0110") return 3;
    return 2;
}

int main() {
    int t;
    cin >> t;
    while(t--) cout << solve() << endl;
}

Python:

def solve():
    n = int(input())
    s = input()
    k = s.count("1")
    if k & 1:
        return -1
    adj = s.count("11")
    if k >= 4 or k == 0 or not adj:
        return k // 2
    if n == 3:
        return -1
    if s == "0110":
        return 3
    return 2


t = int(input())
for _ in range(t):
    print(solve())