# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* notsoloud

*iceknight1093, satyam_343*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1335

# PREREQUISITES:

None

# PROBLEM:

Given a binary string S, in one move you can reverse any substring of length 3. What’s the minimum distance between some pair of ones that you can achieve?

# EXPLANATION:

Suppose we reverse the substring consisting of indices [i, i+1, i+2]. Notice that this is essentially the same as swapping S_i and S_{i+2}.

In particular, if a `1`

is on an even position, then after a move it will remain on an even position; and the same holds for odd positions.

However, among the even positions we can swap ‘adjacent’ elements, which means we can rearrange them as we like. This applies to the odd positions as well.

So,

- If there is a
`1`

on an even position and a`1`

on an odd position, we can rearrange the string to make them adjacent, giving us an answer of 1 (which is obviously the minimum possible). - If the above condition doesn’t hold, then all the ones are on positions of the same parity. In this case, we can make the distance between them 2.

So, all that needs to be done is to iterate across the string and check whether there are ones at both even and odd positions.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Code (Python)

```
for _ in range(int(input())):
n = int(input())
s = input()
odd, even = 0, 0
for i in range(n):
if s[i] == '1':
if i%2 == 0: even = 1
else: odd = 1
print(1 if odd > 0 and even > 0 else 2)
```