Want to solve this problem? Login now to get access to solve the problems
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The only line of each test case contains a binary string 'STR'.
For each test case, print the minimum operations needed to make ‘STR’ beautiful.
Print the output of each test case in a separate line.
1 <= T <= 100
2 <= |STR| <= 10^5
STR[i] = ‘1’ or ‘0’
Where ‘T’ is the number of test cases, ‘STR’ is the given binary string and |STR| denotes the length of ‘STR’.
Time Limit: 1 sec
2
0000
1010
2
0
For the first test case:
The two beautiful strings that can be formed from the given ‘STR’
are “1010” and “0101”. Ninja can transform ‘STR’ to “1010” by
performing the following operations:
Replace ‘0’ at index 0 by ‘1’.
Replace ‘0’ at index 2 by ‘1’.
Ninja can transform ‘STR’ to “0101” by performing the following
operations:
Replace ‘0' at index 1 by ‘1’.
Replace ‘0’ at index 3 by ‘1’.
The minimum number of operations in transforming ‘STR’ to either of the two beautiful strings is 2.
For the second test case:
Given ‘STR’ is already beautiful so the minimum number of operations required is 0.
2
01011
1001
1
2
For the first test case:
The two beautiful strings that can be formed from the given ‘STR’ are “10101” and “01010”. Ninja can transform ‘STR’ to “10101” by performing the following operations:
Replace ‘0’ at index 0 by ‘1’.
Replace ‘1’ at index 1 by ‘0’.
Replace ‘0’ at index 2 by ‘1’
Replace ‘1’ at index 4 by ‘0’.
Ninja can transform ‘STR’ to “01010” by performing the following operations:
Replace ‘1’ at index 4 by ‘0’.
The minimum number of operations in transforming ‘STR’ to beautiful is the minimum of the above two which is 1.
For the second test case:
The two beautiful strings that can be formed from the given ‘STR’ are “1010” and “0101”. Ninja can transform ‘STR’ to “1010” by performing the following operations:
Replace ‘0’ at index 2 by ‘1’.
Replace ‘1’ at index 3 by ‘0’.
Ninja can transform ‘STR’ to “0101” by performing the following operations:
Replace ‘0’ at index 0 by ‘1’.
Replace ‘1’ at index 1 by ‘0’.
The minimum number of operations in transforming ‘STR’ to either of the two beautiful strings is 2.