[Coding] Non Adjacent Flips solution codechef

[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 110110101111111_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

  • 1T1001≤T≤100
  • 1N1001≤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.

Leave a Comment