Subtask 1

With ~10~ bits at most, we can try all possibilities. This can be implemented recursively, where at the ~i^\text{th}~ bit, we choose either to flip it or not. Then we check at the end if it is a valid bitstring, and take the minimum number of flips among all possibilities.

Time complexity: ~\mathcal{O}(2^N)~

Subtask 2

In this subtask, we only need at most 2 bit flips. We can loop all pairs of positions that might change ~(i,j)~, and there are ~4~ possibilities that can be set for the ~i^\text{th}~ and ~j^\text{th}~ positions, each being either 1 or 0. By trying each case, then checking if it is valid, we can see which case causes the least number of switches.

Time complexity: ~\mathcal{O}(N^2)~

Full Solution

We first observe that if we know any ~2~ adjacent bits, then the remaining bits must be fixed.

Consider these cases:

• 11 ~\rightarrow~ the next must be a 0
• 10 ~\rightarrow~ the next must be a 1
• 01 ~\rightarrow~ the next must be a 1
• 00 ~\rightarrow~ the next must be a 0

From this, we can determine that there are ~4~ total possibilities if we fix the first ~2~ bits. But upon construction, we notice that if we start with 11, 10, or 01 it may not be possible to have ~N~ bits. During the construction, we end up with the same group of ~3~ bits being repeated (101, 011, or 110). This means that ~N~ must be a multiple of ~3~ in order to generate a series of bits that contain 11, 10, or 01. Otherwise, the only other option is to set them to be all 0.

To find the sequence of bits with the minimum number of flips, we can first check if ~N~ is a multiple of ~3~. If it is, then generate all ~4~ possibilities by fixing the first ~2~ bits, and then try them all. If ~N~ is not a multiple of ~3~, then it must be all 0, so simply output the number of 1s.