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.