Flip The Bits

The initial string is ‘111….’ we can do any of the four operations that may result in four different strings, then again we can do any four operations on each of these four strings, which may give some other strings, a key point to observe here is that if we do the same operation 2 times on the original string, then we end up with the original string itself. So doing the same operation even no. of times is the same as not doing that operation at all, and doing the same operation odd no. of times is the same as doing operation 1 time only. Also, we can observe the order of operations does not matter. 

For example, let ‘S’ be ‘1001’ performing 1st type operation, and then 2nd type operation will give the string ‘1100’ that is the same as performing 2nd type operation and then 1st type operation. From this, we can say that there are not a very large number of possible final strings. So we can do BFS to perform operations while maintaining a HashSet or unordered_set so that we do not perform operations on the same string twice. 

Algorithm:

• Declare a string ‘S’ of size ‘N’ and all characters as ‘1’.
• Declare a unordered_set of strings to keep track of visited strings on the current level during BFS.
• Declare an empty queue of strings to do the BFS.
• Push ‘S’ into the queue and insert ‘S’ in the set.
• Declare a variable say ‘level’ to keep track of the no. of operations performed, as we have to do operations ‘M’ times only.
• Run a loop until the queue is not empty and ‘level’ is less than ‘M’.
  • Clear the set, i.e delete all elements of the previous level from the set.
  • Let the current size of the queue be ‘len’.
  • Run a loop from i = 0 to ‘len’ to pop all elements at the current level.
    • Pop the element from the queue and store it in say ‘currStr’.
    • Declare an array of size 4 say ‘nextStr’ to store the strings after performing operations.
    • Do 1st type operation on ‘currStr’ and store the resulting string in ‘nextStr[0]’.
    • Do a 2nd type operation on ‘currStr’ and store the resulting string in ‘nextStr[1]’.
    • Do a 3rd type operation on ‘currStr’ and store the resulting string in ‘nextStr[2]’.
    • Do a 4th type operation on ‘currStr’ and store the resulting string in ‘nextStr[3]’.
    • Run a loop from j = 0 to 3
      • If ‘nextStr[j]’ is not in set, then push ‘nextStr[j]’ in the queue and insert it in the set.
  • Increase ‘level’ by 1.
  • If the current size of the set is the same as 'len', it means that now we have visited all the possible strings, so we can break the loop.
• Return the size of the set.

As discussed in the previous approach, there are not many final strings that are possible.

Let's consider all possible cases.

1. When ‘N’ = 1, i.e ‘S’ is ‘1’, it's easy to see that the final string can be ‘1’ or ‘0’.
2. When ‘N’ = 2, i.e ‘S’ is ‘11’, in one operation we can make it ‘00’ with 1st type of operation, ‘01’ with 2nd type of operation, ‘10’ with the second type of operation. After the second operation, we can also get ‘11’ by doing the 1st type of operation on ‘00’. Of Course for operations more than 2 times we can get any of these 4 strings
3. When ‘N’ = 3, i.e. ‘S’ is ‘111’, similarly as above in one operation we can get 4 strings [ ‘000’, ‘010’, ‘101’, ‘011’ ]. And for ‘M’ = 2 i.e after 2 operations, we can get 7 strings :[  ‘000’, ‘001’, ‘010’, ‘100’, ‘101’, ‘110’, ‘111’ ]. For ‘M’ > 3. We can get all possible 8 strings of size ‘3’.
4. When ‘N’ > 3, i.e ‘S’ is ‘1111...’,  In this case, we can observe that adding a new character in a string of size ‘3’ doesn’t affect the number of resulting strings, as the pattern is repeated after the 3rd index. For example, let's say we perform the 2nd type of operation on ‘S’ we get ‘010101….’ repeating pattern after every 2 characters, similarly if we perform 4th type of operation we get ‘011011...’ repeating pattern after every 3 characters, So no matter what operation we do we will get a string with repeating pattern with almost after 3 characters.

So for ‘N’ > 3, the whole string can be uniquely defined by only the first three characters.

Algorithm:

• If ‘M’ == 0, the answer will be only ‘1’, so return 1.
• If ‘N’ == 1, the resulting string can be ‘1’ or ‘0’, so return 2.
• If ‘N’ == 2
  • If ‘M’ == 1, we can get only 3 strings, return 3.
  • If ‘M’ >= 2, we can get all 4 possible strings, return 4.
• If ‘N’ >= 3
  • If ‘M’ == 1, we can get only 4 strings, return 4.
  • If ‘M’ == 2, we can get 7 possible strings, return 7.
  • If ‘M’ >= 3, we can get all possible strings of size 3, so return 8.