Flip The Bits

Easy
0/40
Average time to solve is 25m
profile
Contributed by
22 upvotes
Asked in companies
BarclaysalibabaLTI - Larsen & Toubro Infotech

Problem statement

Ninja has a binary string ‘S’ of length ‘N’. Initially, all the characters in a string are ‘1’, i.e.

S[i] = ‘1’ for each 1 <= ‘i’ <= ‘N’.

An operation is defined as choosing a number between 1 to 4, and doing the following steps accordingly.

1. If the chosen number is 1, then flip all the characters in string.

2. If the chosen number is 2, then flip all the characters at odd indexes.

3. If the chosen number is 3, then flip all the characters at even indexes.

4. If the chosen number is 4, then flip all the characters at (3k + 1) indexes.

You need to find out that after performing operations exactly ‘M’ number of times, how many distinct final strings can be there.

Note : 
1. A binary string is a string in which all characters are either ‘1’ or ‘0’.

2. Flipping a character means that if the character is ‘1’ then change it to 0, or if it is ‘0’ then change it to ‘1’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the size of string and number of operations.
Output Format : 
For each test case, print one integer denoting the number of final strings possible after performing ‘M’ number of operations.

The output of each test case will be printed in a separate line.
Note : 
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N, M <= 5000

Time Limit: 1 sec
Sample Input 1 :
2
3 1
1 2
Sample Output 1 :
4
2
Explanation Of Sample Input 1 :
Test Case 1:
We can get these final strings [ ‘000’, ‘010’, ‘101’, ‘011’ ]  by doing four types of operations.

Test Case 2:
We can get ‘1’ by doing the 1st type of operation twice and ‘0’ by doing the 1st type of operation followed by the 3rd type of operation.
Sample Input 2 :
2
2 10  
4 3
Sample Output 2 :
4
8
Hint

Try to generate all strings using BFS.

Approaches (2)
BFS Approach

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.
Time Complexity

O(N), where ‘N’ is the given size of the string.

 

Doing operations on a string takes O(N) time. we are doing insert and find operation in an unordered_set that takes O(N) time as we need to do a deep copy of string for inserting it that takes linear time. Also In the worst-case BFS loop will only run at most ‘4’ times as doing the same operation twice in a string would result in an already visited string. So there can only be 4 levels at most in the BFS. Hence the overall time complexity is O (N).

Space Complexity

O(N),  where ‘N’ is the given size of the string.

 

As we are storing strings that take O(N) space. We are also using a set data structure of strings but in the worst case, the set will contain string less than 10 strings. Also, we are using a queue that at most will contain less than 10 strings at a time which takes constant space. Hence the overall space complexity will be O(N)

Code Solution
(100% EXP penalty)
Flip The Bits
Full screen
Console