Bit flipping algorithm

The goal is to flip all the bits in the same direction (I mean all to be 1 )

For example, we have:

0110011

We need to flip the bits so that we get

1111111

We can only flip K consecutive bits at a time.

I need the algorithm to find the smallest number of flip N of given the value of K.

Example:

input -> output

Example 1:

00010110, k=3 -> n=3

(because : first flipping the leftmost 3 zeros, getting to 11110110, then the rightmost 3, getting to 11110001, and finally the 3 zeros that remains . There are other ways to do it with 3 flips or more, but none with fewer than 3 flips.)

Example 2:

11111, k=4 -> n=0

(because : every bits are already 1, there is no need to flip)

Example 3:

01010, k = 4 -> n = IMPOSSIBLE

(because: there is no way to make the second and third bits from the left to be '1' at the same time, because any flip flips them both. Therefore, there is no way to make all of the bits '1'.)

The usual observations apply here: You have $n-k+1$ different types of flip available which we can number by the first bit flipped from $1$ to $n-k+1$. The flips commute, so it doesn't matter what order we do them, just which ones we do. There is no reason to use a type more than once because the second use undoes the first. The only flip that affects bit $1$ is flip $1$, so do it or not and get bit $1$ right. Now the only flip you have left that affects bit $2$ is flip $2$, so get bit $2$ right. Keep going. When you run out of flips, see if you have the desired result. If not, declare failure.

This gives the minimum number of flips because if bit $1$ is wrong you have to use flip $1$. If bit $2$ is then wrong, you need to use flip $2$ and so on. We can see there are only $2^{n-k+1}$ accessible states out of the $2^n$ possible bit patterns.

• I think the OP is asking for an algorithm that does the job with the minimal number of flips. Does this one? – Ethan Bolker Apr 8 '17 at 17:51
• @EthanBolker: yes, it does. If bit 1 starts out wrong, you have to flip it so can't get away without flip 1. If bit 2 is then wrong, you have to flip it, and so on. We can see that there are only $2^{n-k+1}$ accessible states – Ross Millikan Apr 8 '17 at 17:59
• Clear and elegant thanks. I think you should edit this observation into the answer. – Ethan Bolker Apr 8 '17 at 18:06
• @RossMillikan Thanks, I appreciate your answer +1 – TSR Apr 8 '17 at 18:50
• @RossMillikan however, I realize that you suggest a brute force algorithm, which works properly, but might not be the most efficient when it comes to a large dataset (with a bit string with 1000 length for instance). But I assume that there should be a compact formula that correlates with k in order to find n. Thanks – TSR Apr 8 '17 at 18:52

Ross' solution is correct in that the method does find the minimal number of flip.

The idea is that we can visit each bit from the left to the right and flip the next $$k$$ bits. If one really code it up in the sense of visiting a bit and flipping the next $$k$$ bits directly, the complexity of the algorithm is $$O(nk)$$.

We can actually solve the problem in $$O(n)$$ times and $$O(n)$$ memory. The idea is to control the number of time we flip the bits at each position and use an additional variable instead.

An analogy is to think of the bits as a series of rooms with lights. A forgetful general visited the first room, he tells one of his soldier to push the switch for the consecutive $$k$$ rooms. But rather than running to the next $$k$$ rooms and push the switch immediately, he just keep a record on when should he stop pushing the switch accoding to this current instruction.

Just before the general enter the next room, the soldier implement the existing instruction for the current room. The main difference is rather than having to press a switch everytime an instruction is given, two instruction might cancels out each other for a particular room.

For example, if we have a very long string, $$k=50$$. Each time an instructionis given, the soldier doesn't run for the next $$50$$ rooms immediately, instead he will just take note that the instruction expired after the next $$50$$ rooms. Hence if a new instruction is given on the very next day and no further instruction is given after that. He doesn't have to press any switch for quite some time, he just have to remember if the net instruction if still active. On the days that the instruction expired, he has to change the instruction again.

def minKBitFlips(A, k):
n = len(A)
future_switch_order = [0 for i in range(n)]
switch = 0
ans = 0
for i in range(n):
switch ^= future_switch_order[i]
if A[i]^switch == 0:
ans += 1
switch ^= 1
if i+k < n:
future_switch_order[i+k] = 1
elif i+k > n:
return -1
return ans

print(minKBitFlips([0,0,0,1,0,1,1,0], 3))
print(minKBitFlips([1,1,1,1,1], 4))
print(minKBitFlips([0,1,0,1,0], 4))