PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You are given a binary string S of length N. You can perform the following operation on S:
Pick any set of indices such that no two picked indices are adjacent.
Flip the values at the picked indices (i.e. change 0 to 1 and 1 to 0).
For example, consider the string S = 1101101.
Pick the indices \{1,3,6\}.
Flipping the values at picked indices, we get \underline{1}1\underline{0}11\underline{0}1→0111111.
Note that we cannot pick the set \{2,3,5\} since 2 and 3 are adjacent indices.
Find the minimum number of operations required to convert all the characters of S to 0.
EXPLANATION:
For each test case we have a binary string of length N.
Now as no adjacent bits can be flipped together. Three cases are possible:
- When the string is already 0, then the number of minimum operations will be zero.
- When no two adjacent bits are set. In this case all the set bits can be converted to 0 in 1 operation.
- When the string contains adjacent set bits. In this case it can be shown that the answer will be 2 since all the odd-indexed set bits and even-indexed set bits can be identified as two different sets.
Evaluating all the above possibilities gives us the result.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution