9
$\begingroup$

Source: My school teacher, it was just given as a problem statement.

Problem: You are given a binary sequence $S$ of up to $10^6$ bits. You wish to set all the bits in the string to $1$, but the catch is that you are only allowed to flip bits in adjacent pairs! Specifically, pairs of identical bits (i.e. $11$ and $00$ — flipping them would result in $00$ and $11$ respectively)! You may not flip bits individually, and the paired bits must be identical.

If it is possible, calculate the minimum number of flips necessary to set all the bits in the string to $1$, otherwise output no!

Example: $S = 0110$. The minimum number of flips necessary would be $3$: $0110 \rightarrow 0000 \rightarrow 1100 \rightarrow 1111$.

This is a mental exercise provided to us over this weekend. Algorithmically, this is a simple backtracking problem. However, my teacher hinted that this isn't necessarily meant to be an algorithmic question, but more of a puzzle. Whilst I have solved this using backtracking, I wish to gather some intuition on the puzzle-side of this!

$\endgroup$
3
  • $\begingroup$ The tag I just added is a hint. $\endgroup$
    – RobPratt
    Feb 10 at 17:17
  • 2
    $\begingroup$ To be clear, the paired bits you flip must be adjacent? $\endgroup$
    – xnor
    Feb 10 at 18:35
  • $\begingroup$ @xnor Yes, correct $\endgroup$
    – user88178
    Feb 10 at 19:31

3 Answers 3

8
$\begingroup$

Find a good invariant

One always flips an odd and an even positioned bit, so (even positioned zeros) - (odd positioned zeros) remains the same.
Thus required for a solution: an equal number of odd positioned and even positioned zero's.

You need to see if if you can work towards the solution

If we have even and odd positioned zero's, there is a pair (e.g. if the nth zero is odd positioned and the (n+1)th zero even they are a pair of have a pair of 1s in between)

If we flip the first pair we either flip the first bit (and can make it 1) or have created a pair 1 position closer to the start (continue flipping towards the start until the first bit is 1.

If we now exclude the first bit from the sequence, we have a smaller sequence with still adheres to the invariant. Thus we can flip the new first to 1 too, using the same method, and repeat until the sequence size is 1.
The last bit must be 1 due to the invariant.

So, requiring an equal number of even and odd positioned zeros is a sufficient condition.

To find the number of flips needed:

One can 'move' a bit 2 position using 2 adjacent flips (and not faster), move zeros until they all form pairs and then flip them all seems optimal..
example
01010101101010101001 Number odd and even positioned zeros to get:
1-2-3-4--1-2-3-4-55-
It takes 4 double-moves each to get the 1s,2s,3s and 4s together and then 5 moves to flip them to 1, for a total of 37 flips.

$\endgroup$
3
  • $\begingroup$ I found your solution steps a bit confusing to read, but there is really only one way to remove such a pair of zeroes - flip all the ones between them (if any) to zero, then flip that block of zeroes including the pair. There is one minor problem - the choice of pairs can make a difference in the number of flips needed. For example with 01100110 you should not pair the middle two zeroes, since that uses two moves too many. I think that working from left to right (i.e. choose your $n$ as small as possible), will always lead to an optimal solution. $\endgroup$ Feb 11 at 12:48
  • $\begingroup$ @JaapScherphuis Since the question was for intuition, not a detailed final answer, I left the last part (maybe too) short. However, I said move 2 positions until ALL form pairs i.e. 01100110 to e.g. 11000011 or 11001100 for a total of 6 flips which is minimal. Flipping the middle 00 does not help achieve all-pairs and is (thus) indeed suboptimal. $\endgroup$
    – Retudin
    Feb 11 at 15:22
  • $\begingroup$ I see now. I was thinking that with e.g. 0111011010 you would have to pair and remove the inner zeroes before you could pair and remove the outer zeroes. Instead, you are shifting for example the third zero to the left to pair with the first zero like this: 0111011010 -> 0111001110 -> 0110011110 -> 0011011110. The two flips used to move the zero to the left are a reversed when it jumps over a 0 (110->000-> 011 and 100->111-> 001) but that does not really matter. Conceptually I find it nicer to pair them like nested brackets (12344321, not 12341234) but the result is the same. $\endgroup$ Feb 12 at 10:56
8
$\begingroup$

This is a refinement of @Retudin's very nice invariant which makes it easy to calculate the required number of flips in linear time:

Given a binary string, for example, 110110010110101 split it in two at each possible position:

  • 1 + 10110010110101
  • 11 + 0110010110101
  • 110 + 110010110101
  • 1101 + 10010110101
  • ...

and for each fragment compute the Retudin imbalance (RI): # of zeros in odd positions - # of zeros in even positions. For any split position i the sum of RI for both fragments $c = RI_\text{left}(i) + (-1)^i RI_\text{right}(i)$ will be the same, c=0 if and only if the string is solvable. As in this case the absolute RI (ARI) is the same for both fragments we can treat it as a function ARI(i) of the split position i. The total RI (TRI) is the sum of ARI(i) over all split positions i.

Theorem: The minimal number of flips needed is given by TRI.

This follows from

Lemma: Let us specify flip F(i) by the position between the two bits flipped. Then applying F(i) modifies ARI(i) by +/-1 and leaves all other ARI(j) unchanged.

Lemma: Unless the string is all 1s there is always a position i such that F(i) is legal and reduces ARI(i) by 1.

Proof: Let m=ARI(j) be the maximal ARI(j) and WLOG let there be m more zeros in odd positions than in even positions in the left fragment and vice versa in the right fragment. The last 0 on the left side and the first 0 on the right side must be in odd and even position, respectively (otherwise m is not maximal). The two positions are therefore either directly adjacent or separated by a block of 1s of even length. In the first case we can can flip the two zeros directly reducing the number of majority-parity zeros in either fragment, in the second case we can split the block of ones into two odd sized sub-blocks and flip at this position adding a minority-parity 0 to either fragment.

$\endgroup$
0
$\begingroup$

Which strings can be brought to all-1s?

Every flip flips two bits. Either both change from 1 to 0, both change from 0 to 1, or a 1 and 0 switch. Either way, the parity of the number of 0s remains the same. If this parity is odd, return "No."
Every string with an even number of 0s can be reduced to all-1s, by induction on the length of the section with 0s. If the section has length 2, then it is 00 and one flip will clear it. If the section is longer, flip the first 0 - the result still has an even number of 0s, but since the first 0 is now a 1, the length of the section with 0s decreases by at least 1.

How do you optimally solve a string?

First note that no optimal solution will flip a bit outside of the part containing 0s. Every such bit must flip an even number of times - take the furthest one (such that all of its evenly-many flips use the same neighbor) and remove its flips to obtain a shorter solution.
From this, we gather that we must perform a flip with the leftmost 0 and its right neighbor no matter what, so we may as well do it. Repeating this argument as many times as necessary tells us that the solution method used in our earlier proof in face yields an optimal solution for any solvable input.

How many moves will this take?

To find this out, simply look at the leftmost two 0s. If they have n 1s between them, they'll take n+1 moves to clear by the above algorithm, so add n+1 to your move count, set those two 0s to 1, and continue with the next two 0s, if they exist.

$\endgroup$
4
  • 1
    $\begingroup$ "and the paired bits must be identical." And adjacent. Meaning that a string of alternating 1s and 0s cannot be flipped. Maybe the OP misunderstood that requirement, since it seems unlikely to be what the teacher would ask. $\endgroup$
    – JLee
    Feb 11 at 2:47
  • 2
    $\begingroup$ Yea @JLee mentioned the oversight i made too. For example, "0101" is not solvable. $\endgroup$ Feb 11 at 3:29
  • 2
    $\begingroup$ @JLee It is indeed what the teacher wants. He is aware that some examples have no solution! $\endgroup$
    – user88178
    Feb 11 at 5:03
  • $\begingroup$ Ok. Thx for clarifying $\endgroup$
    – JLee
    Feb 11 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.