Last Updated: 25 Apr, 2021

Binary Flip

Hard

Asked in company

Solve now

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The main idea is to efficiently use segment tree data structure to solve the queries.

In every node of the segment tree sgt will store the number forming in the range denoting the node % 3.

Eg: in the above example we have string “010001” in the range [l, r], we are dividing it into two equal parts [l, m] and [m+1, r], where m = (l+r)/2. And calculating values recursively for the two divided parts. After finding the answer for both we are combing them.

We can see that the binary string in range [l, r] is “010001” which is formed by concatenation of “010” and “001”. Or we can say that it is formed by shifting “010” 3 times to the right ( or multiplying by 2^3) making it “010000” ( after shifting right ). And adding “001” to it.

In segment tree solution we will be doing the same thing. We will recursively calculate the answer for the two halves, then add them using the same logic.

sgt[i] = ( sgt[2*i+1]* ( 2^(r-m)%3 ) + sgt[2*i+2] )%3.

r-m, will the length of the string on the right subtree and 2^i % 3 can be pre calculated to make it easier.

Solve now