PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given a binary string S. Determine a sequence of at most |S| operations to make all characters of S equal '0'.
The operations are:
- Select 3 consecutive characters of S whose values are not all equal, and flip the values of the characters.
- Select a single character of S and flip its value.
You may not perform the same operation two times in a row.
EXPLANATION:
Lemma: In any valid solution, the last operation performed on S will always be an operation of type 2.
Proof
An operation of the first type always flips a non-zero number of 0 characters, so it can’t be the last operation (since a character with value 1 would still exist after performing it).
Thus, the last operation performed is always of type 2.
Claim: If a solution exists, then the first operation is always
- of type 1, if the number of 1's in S is even, and
- of type 2, otherwise.
Proof
It isn’t hard to deduce that both operations either increment or decrement the number of 1's in S by exactly one. Thus, an even/odd number of operations changes the number of 1's in S by an even/odd count.
Let x equal the number of 1's in the original string S.
Then, since we want to decrease the number of 1's in S by x, we have to perform an odd/even number of operations when x is odd/even. Therefore, since operation of type 2 should be the last operation (by the above lemma), and we have to perform the operations alternatively, it follows that the first operation to perform is
- of type 1 when x is even, and
- of type 2 otherwise.
Armed with this, we can solve the rest of the problem constructively!
For the trivial (but important!) case where S is an even length string comprising of 1's only, it is easy to see that no solution exists.
Why?
The claim above implies the first operation should be of type 1. But how will you do a type 1 operation when all characters are the same?
I claim that a solution always exists for all other cases.
The rest of the solution is constructive.
Hint 1
Assume there exists no constraints on the number of operations that can be performed. Can you construct a solution then?
Hint 2
Let x represent the largest positive integer such that the first x characters of S are equal to 1.
Try transforming S[..x] to all zeros, using atmost x+1 operations. If you do this, you can do the same on substring S[x+1..] recursively.
Hint 3
Try constructing a solution for each of the following values of S:
- 010
- 110
- 10001
- 011011
- 1110001
- 1111000101
Try generalizing your method.
My solution
Different methods were used by the panel to solve this problem. I don’t claim mine is the best, but it surely is the most intuitive 
.
Let curr represent the type of the operation that we must perform next. Initially, curr=1 if the number of 1's in S is even, and 2 otherwise.
Step 1: If curr=2, flip the first character of S whose value is 1.
Step 2: Let x represent the largest positive integer such that the first x characters of S are equal to 1. Then, transform S[..x] to all zeros, using atmost x+1 operations.
How?
If x=0, then we have to do nothing.
Otherwise, the sequence of operations we can apply is given below. Observe that Step 1 forces the first operation in this step to always be of type 1.
When x is even -
v This is index x
11...111110...... // Initial string S
11...111001...... // Operation1 at index x-2
11...111000...... // Operation2 at index x
11...100100...... // Operation1 at index x-4
11...100000...... // Operation2 at index x-2
.
.
.
001...00000...... // Operation2 at index 0
000...00000...... // Operation1 at index 2
The number of operations performed in this case is equal to x.
Similarly (almost), when x is odd -
v This is index x
11...111110...... // Initial string S
11...111101...... // Operation1 at index x-1
11...111100...... // Operation2 at index x
11...110010...... // Operation1 at index x-3
11...110000...... // Operation2 at index x-1
.
.
.
001...00000...... // Operation2 at index 0
000...00000...... // Operation1 at index 2
Exactly x+1 operations are performed in this case.
So, using the above steps, we have been able to transform all characters of S[..x] into zeros, using at most x+1 operations.
Repeat the above steps on substring S[(x+1)..] recursively, while S is not all zeros. It is easy to see that the recursion terminates, and that we use at most |S| operations overall!
See the code linked below for implementation details.
Corner case (important!)
When S=01111, we can no longer apply Step 2 on S[1..] (in step two, we made an assumption that a character whose value is 0 always exists, thus the inconsistency).
This case is however, trivial to tackle, and left to the reader as an easy exercise (see my code linked below for details)!
TIME COMPLEXITY:
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters