[Coding] 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).

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.

[Coding] Non Adjacent Flips solution codechef

• 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.

Output Format

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

[Coding] Non Adjacent Flips solution codechef

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

Sample Input 1 

3
6
101001
5
00000
3
111

[Coding] Non Adjacent Flips solution codechef  

1
0
2

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.

• ANSWER

  “Click Here“