# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Utkarsh Gupta

Tester: Abhinav Sharma, Nishank Suresh

Editorialist: Pratiyush Mishra

# DIFFICULTY:

Easy

# PREREQUISITES:

None

# PROBLEM:

You are given a binary string S of length N. You can perform the following operation on S:

Pick any set of indices such that no two picked indices are adjacent.

Flip the values at the picked indices (i.e. change 0 to 1 and 1 to 0).

For example, consider the string S = 1101101.

Pick the indices \{1,3,6\}.

Flipping the values at picked indices, we get \underline{1}1\underline{0}11\underline{0}1→0111111.

Note that we cannot pick the set \{2,3,5\} since 2 and 3 are adjacent indices.

Find the **minimum** number of operations required to convert **all** the characters of S to 0.

# EXPLANATION:

For each test case we have a binary string of length N.

Now as *no adjacent bits can be flipped together*. Three cases are possible:

- When the string is already 0, then the number of minimum operations will be
**zero**. - When
**no two adjacent bits are set**. In this case all the set bits can be converted to 0 in**1**operation. - When the string contains adjacent set bits. In this case it can be shown that the answer will be 2 since all the odd-indexed set bits and even-indexed set bits can be identified as
**two different sets**.

Evaluating all the above possibilities gives us the result.

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester-1’s Solution

Tester-2’s Solution