PROBLEM LINK
CONTEST PANEL
Author: Ildar Gainullin
Tester: Oleksandr Kulkov
Editorialist: Prateek Gupta
DIFFICULTY
EASY
PROBLEM
Given a binary string, you need to transform this into a string consisting of only zeros by applying a specific operation number of times. The operation allows you to choose a prefix of the string and flip all the bits i.e ‘0’ to ‘1’ and ‘1’ to ‘0’.
EXPLANATION
The key is to observe that we need to reverse iterate the string and maintain the state as to how many times we have applied the given operation. When you reverse iterate the string and apply the operation on some index, it will affect the whole prefix S[0..\ index\ -\ 1]. Having said that, when we arrive at a particular index in the string, we already know the number of operations that have been applied till now. Based on the digit at this index and number of operations applied, we decide what is the actual digit at this position. If it is ‘0’, we move forward, else we again flip the bits for a prefix ending at this position. Below is the simple pseudo code which will help you to understand things much better.
operations = 0
for ( i = s.length() - 1 to i = 0 ) {
if ( digit(i) ^ operations ) {
operations ^= 1;
}
}
It must be clear from the above snippet, that in case the number of operations are even, the state of the current bit will remain same, otherwise (bit ^ 1). Since, we are traversing a string once, the overall complexity will be O(N) where N is the length of the given string. For details on the implementation, have a look at the author or tester’s solution.
SOLUTIONS
Author solution can be found here.
Tester solution can be found here.