0

Binary Flip

Difficulty: HARD
Contributed By
Achint Narang
Avg. time to solve
15 min
Success Rate
85%

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.

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
Reset Code
Full screen
copy-code
Console