Binary Flip

Hard
0/120
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in company
Grofers

Problem statement

You are given a binary string of size ‘N’, and ‘Q’ queries to work on.

The queries are of two types:

i) 1 ‘l’ ‘r’, denoting that the query is of type-1, and you have to return the integer forming from binary string in range [l, r] % 3.

ii) 2 ‘idx’, denoting that the query is of type-2, and you have to flip the bit at position ‘idx’.

Eg: If S=”010010”, in query-2 if ‘l’= 0, and ‘r’= 4, then then we will take the substring “01001” which is 9, thus our answer will be 9%3 = 0.

Note: l, r, idx are in 0-based indexing.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘N’, denoting the length of binary string ‘S’.

The next line contains the binary string ‘S’.

The next line contains an integer ‘Q’, denoting the number of queries.

The next ‘Q’ lines contain the queries of type-1 or type-2. The two types of queries are: 
i)  1 ‘l’ ‘r’, denoting that the query is of type-1, and you have to return the integer forming from binary string in range [l, r]  % 3.
ii) 2 ‘idx’, denoting that the query is of type-2, and you have to flip the bit at position ‘idx’.
Output Format : 
For each query of type-1 return the number forming in the range % 3.

Note: Don't print anything it has already been taken care of. Just implement the given functions.
Constraints : 
1 <= N, Q <= 3000
0 <= l, r, idx <= N - 1

Time Limit: 1 sec
Sample Input 1 :
5
10010
5
1 0 4
2 1
1 0 3
2 3
1 1 4
Sample Output 1 :
0
1
2
Explanation for Sample Input 1 :
S=”10010”

Query 1: [0, 4] we will have substring  “10010”, which is (2+16)%3 = 0

Query 2: flip bit at position 1, i.e. flip S[1], which makes,  S=”11010”

Query 3: [0, 3] we will have substring  “1101”, which is (1+4+8)%3 = 1

Query 4: flip bit at position 3, i.e. flip S[3], which makes,  S=”11000”

Query 5: [1, 4] we will have substring  “1000”, which is (8)%3 = 2
Sample Input 2 :
7
0111110
7
2 4
1 5 6
1 6 6
2 1
2 6
1 3 3
1 0 6
Sample Output 2 :
2
0
1
0
Hint

Brute force the queries, calculate answer for each query in linear time

Approaches (2)
Brute Force

In the query of type-1, just iterate over the string ‘S’ in the range [l, r] to calculate the answer.

 

In the query of type-2 just flip the value in the original string ‘S’.

 

In the type-1 query, we calculate the answer for the range [l, r] by first calculating the answer for range [l, i], then calculating [l, i+1] from the previous value. 

 

The answer for the range [l, i+1] will be the answer calculated by [l, i] time 2 (or shifting it left) + bit at the position i.

Time Complexity

O( Q*N ),  where N is the length of string ‘S’ and ‘Q’ is the number of the queries.

 

In the worst case, we are iterating over the whole string for each of the queries.

Space Complexity

O(1)

 

No additional space is required.

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