[Solution] Non Adjacent Flips solution codechef

Non Adjacent Flips solution codechef – You are given a binary string SS of length NN. You can perform the following operation on SS:

• Pick any set of indices such that no two picked indices are adjacent.
• Flip the values at the picked indices (i.e. change 00 to 11 and 11 to 00).

[Solution] Non Adjacent Flips solution codechef

For example, consider the string S=1101101S=1101101.
If we pick the indices {1,3,6}{1,3,6}, then after flipping the values at picked indices, we will get 1⎯⎯10⎯⎯110⎯⎯1→01111111_10_110_1→0111111.
Note that we cannot pick the set {2,3,5}{2,3,5} since 22 and 33 are adjacent indices.

Find the minimum number of operations required to convert all the characters of SS to 00.

Input Format

• The first line contains a single integer TT – the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer NN – the length of the binary string SS.
• The second line of each test case contains a binary string SS of length NN.

[Solution] Non Adjacent Flips solution codechef

For each test case, output the minimum number of operations required to convert all the characters of SS to 00.

Constraints

• 1≤T≤1001≤T≤100
• 1≤N≤1001≤N≤100

Sample Input 1 

3
6
101001
5
00000
3
111

Sample Output 1 

1
0
2

Non Adjacent Flips solution Explanation

Test Case 11: Pick the set of indices {1,3,6}{1,3,6}. On flipping the values at these indices, the string becomes 000000000000.

Test Case 22: The string already has all characters equal to 00.

For Solution

“Click here“