Update appNew update is available. Click here to update.
Last Updated: Jun 30, 2023
Medium

Count and Toggle Queries on Binary Array

Author Gunjan Batra
0 upvotes

Introduction

Hello Ninjas! Welcome back! We are here again with another concept of the binary array i.e.Count and Toggle Query.  In this blog, we will learn about the count and toggle queries on the binary array. 

Count and Toggle Queries on Binary Array.

We will also see the implementation of the code in C and C++ programming languages. Also, we will learn about the application of count and toggle queries on the binary array. 

Count and Toggle Queries

This is the concept where both are applied to the binary array.

Count Query is used when there is a need to calculate the number of specific bits it appears in any piece of code. We can define it as count (start, end) which will count frequency of 1’s at intervals from start to end.

For example:
Let’s assume a binary number: 010011 which is equivalent to 19
After applying query count(1,3) it will give output as 1
Explanation: from range 1-3 only 1 1’s is present.

Other Example:

Input: arr [ ] = {1, 1, 1, 0, 0, 1, 0}
Output: 4

Input: arr  [ ] = {1, 1, 1, 0, 1, 1, 1}
Output: 6

Input: arr [ ] = {0, 0, 1, 1, 0, 0, 0}
Output: 2

C++ Implementation:-

Function for finding the number of 1’s in a sorted binary array

def countOnes(Arr, left_element, right_element):

# if last element in the array is 0, no 1’s can
	# be present in the array because it is already sorted
	if Arr[right_element] == 0:
		return 0
	# if first element in the array is 1, we know all its elements are
	# are 1’s as the array is already sorted
	if Arr[left_element] == 1:
		return right - left + 1
	# divide array into left and right subarray and recursion
	middle = (left_element + right_element) // 2
	return countOnes(Arr, left_element, middle) + countOnes(Arr, middle + 1, right_element)
if __name__ == '__main__':
	Arr = [0, 0, 0, 0, 1, 1, 1]
	print(countOnes(Arr, 0, len(Arr) - 1))

Toggle Query:

  • Toggle Query is used when there is a need to flip the bits in a specific range of code.
  • We can define it as a toggle (start, end) that will flip the bits in the given range mentioned from start to end.

For example:

Let us assume binary no as considered above: 010011, which is equivalent to 19. After applying query toggle(1,3), it will give output as 101011.

Explanation: The query will flip the bits as 0 to 1 and 1 to 0 in a specific range as given in the query by the user. Hence, it flips the bits from 1 to 3 and gives the output as 101011, which is equivalent to 43.

C Implementation:-

#include <stdio.h>
void binary(unsigned int n)
{
	unsigned int mask = 0x80000000;
    while(mask) {
	  printf("%d", (n&mask)?1:0);
	  mask = mask >> 1;
	}
}
void main()
{
    unsigned int num = 0;
    printf("Enter an integer: ");
    scanf("%d", &num);
    printf("Binary represntation of the input number:\n");
    binary(num); 
    num = ~num;
    printf("\n\nAfter toggling all bits of the number:\n");
    binary(num);
    printf("\n");
}

Now that we are aware of the count and toggle query, it's time to implement them together. Consider an example where binary no is: 0110001

And the instructions are as follows:

Toggle (0, 3)
Toggle (4, 6)
Count (1, 5)
Toggle (2, 4)
Count (1, 2)
Here, the range is as (L, R)

Step1: toggle(0,3) will give output as 1000001
Step2: toggle(4,6) will give output as 1001111
Step3: count(1,5) will give output as 3
Step4: toggle(2,4) will give output as 1110111
Step5: count(1,2) will give output as 2

Now let’s try to understand toggle and count queries on a binary array together. You are given a binary array that has a number of 0’s and 1s and q queries. q can be large! For each query, you are given a certain range [L, R] where L represents the starting range, i.e., left, and R represents the ending range, i.e., right.

suppose arr [ ] = {1,0,0,1}
L = 1 , R = 3 .
do toggling , resultant array = {0,1,1,1}
L = 1 , R =4
count all one's , ans = 3.

So, now we have to keep this thing in mind that we have to either toggle bits in the given range i.e., make 0 = 1 and 1 = 0, on in simple words, alternate it, and on another query in which we have to count all 1’s in the range of [Left, Right].

1.	#include<bits/stdc++.h> 
2.	#define ll long long 
3.	#define mod 1000000007 
4.	#define mp make_pair 
5.	#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
6.	#define pb push_back 
7.	#define endl '\n' 
8.	#define pii pair<int,int> 
9.	#define all(v) v.begin(),v.end() 
10.	ll poww(ll x,ll y) {ll res=1;x%=mod; for(;y;y>>=1){if(y&1)res=res*x%mod;x=x*x%mod;}return res;} 
11.	using namespace std; 
12.	 
13.	int a[25][100005],seg[25][400005],n,lazy[25][400005]; 
14.	 
15.	void build(int i,int l,int r,int x){ 
16.	 
17.	if(l>r) 
18.	return; 
19.	if(l==r){ 
20.	seg[i][x]=a[i][l]; 
21.	return; 
22.	} 
23.	int mid=(l+r)/2; 
24.	build(i,l,mid,x*2+1); 
25.	build(i,mid+1,r,x*2+2); 
26.	seg[i][x]=seg[i][x*2+1]+seg[i][x*2+2]; 
27.	 
28.	} 
29.	 
30.	void setbit(int i){ 
31.	 
32.	int x=a[24][i]; 
33.	int c=0; 
34.	while(x>0){ 
35.	a[c++][i]=x%2; 
36.	x/=2; 
37.	} 
38.	 
39.	} 
40.	 
41.	ll sum(int i,int ql,int qr,int l,int r,int x){ 
42.	 
43.	if(l>r||ql>r||qr<l) return 0; 
44.	 
45.	if(lazy[i][x]){ 
46.	 
47.	seg[i][x]=(r-l+1)-seg[i][x]; 
48.	 
49.	if(l!=r){ 
50.	lazy[i][2*x+1]^=lazy[i][x]; 
51.	lazy[i][2*x+2]^=lazy[i][x]; 
52.	} 
53.	 
54.	lazy[i][x]=0; 
55.	 
56.	} 
57.	 
58.	if(ql<=l&&qr>=r) return seg[i][x]; 
59.	 
60.	int mid=l+r>>1; 
61.	return (sum(i,ql,qr,l,mid,x*2+1)+sum(i,ql,qr,mid+1,r,2*x+2)); 
62.	 
63.	} 
64.	 
65.	void upd(int i,int ql,int qr,int l,int r,int x){ 
66.	 
67.	if(lazy[i][x]){ 
68.	 
69.	seg[i][x]=(r-l+1)-seg[i][x]; 
70.	 
71.	if(l!=r){ 
72.	lazy[i][2*x+1]^=lazy[i][x]; 
73.	lazy[i][2*x+2]^=lazy[i][x]; 
74.	} 
75.	 
76.	lazy[i][x]=0; 
77.	 
78.	} 
79.	 
80.	if(l>r||ql>r||l>qr) return; 
81.	 
82.	if(ql<=l&&r<=qr){ 
83.	 
84.	int temp=5123123; 
85.	temp=seg[i][x]; 
86.	temp=seg[i][x]=(r-l+1)-seg[i][x]; 
87.	temp=2; 
88.	if(l!=r){ 
89.	lazy[i][2*x+1]^=1; 
90.	lazy[i][2*x+2]^=1; 
91.	} 
92.	return; 
93.	} 
94.	int mid=l+r>>1; 
95.	upd(i,ql,qr,l,mid,x*2+1); 
96.	upd(i,ql,qr,mid+1,r,x*2+2); 
97.	seg[i][x]=seg[i][x*2+1]+seg[i][x*2+2]; 
98.	 
99.	} 
100.	 
101.	int main() 
102.	{ 
103.	fast; 
104.	//freopen("C:/Users/PRAJAL/Desktop/input.txt", "r+", stdin); 
105.	//freopen("C:/Users/PRAJAL/Desktop/input5.txt", "w+", stdout); 
106.	 
107.	cin>>n; 
108.	 
109.	for(int i=0;i<n;++i) cin>>a[24][i]; 
110.	for(int i=0;i<n;++i) setbit(i); 
111.	for(int i=0;i<20;++i) build(i,0,n-1,0); 
112.	 
113.	int m,l,r,x; 
114.	cin>>m; 
115.	 
116.	while(m--){ 
117.	 
118.	cin>>x>>l>>r; 
119.	l--; 
120.	r--; 
121.	if(x==1){ 
122.	ll ans=0; 
123.	for(ll i=0;i<20;++i) 
124.	ans+=sum(i,l,r,0,n-1,0)<<i; 
125.	cout<<ans<<endl; 
126.	} 
127.	else{ 
128.	cin>>x; 
129.	for(int i=0;i<20;++i,x/=2) if (x%2) upd(i,l,r,0,n-1,0); 
130.	} 
131.	 
132.	} 
133.	return 0; 
134.	}

 

Also see, Morris Traversal for Inorder and Rabin Karp Algorithm

Application and Features

  • One of the important applications for count and toggle query is digital counters in digital electronics, and as Digital counter is the biggest application of flip-flop where we have to change the state of a flip from off i.e. 0, to on, i.e. 1
     
  • And as we know, this count and toggle query approach is based on a segment tree. It is used in Relational Database Management Systems for query improvisation. It is often used with the Binary Index tree. A segment tree is also used in the fragmentation of disks during an external sort.

Must Read Shift Registers in Digital Electronics

Frequently Asked Questions

What is an Array?

An array is a collection of similar data types elements stored in a contiguous form in the memory. This data structure is one of the simplest ones that we use for storing data, and we can also directly access the element using their indexes. 

What is the application of the count & toggle query?

An important application for count and toggle queries is digital counters in digital electronics.

On what approach is the count & toggle query approach based?

This count and toggle query approach is based on a segment tree. It is used in Relational Database Management Systems for query improvisation. 

Conclusion

A simple solution for this problem is to traverse the complete range for “Toggle” query and when you get “Count” query then count all the 1’s for a given range. But the time complexity for this approach will be O(q*n) where q=total number of queries.

An efficient solution for a given problem is to use Segment Tree with Lazy Propagation. Here we collect the updates until we get a query for “Count”. When we get the query for “Count”, we make all the previously collected Toggle updates in an array and then count a number of 1’s within the given range.

Recommended Problems - 

Previous article
Subsequence Vs Substring
Next article
Shortest Palindrome