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

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.

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.

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