Count Set Bits in Index Range [L, R] in Given Array for Q Queries

Approach

Here, we will take a similar approach to the prefix sum calculation. 

• First, declare an array preSetbits[ ]. preSetbits[i] will store the total count of set bits upto ith index of the given array.
  preSetbits[0] = countofSetbits(arr[0])
   
• Then, iterate over the given array, and find the count of set bits for the ith element of the array. preSetbits[i] will be the sum of the number of set bits present in arr[i] and preSetbits[i-1].
  i.e. preSetbits[i]=preSetbits[i-1] + countofSetbits(arr[i])
   
• Now we can use the preSetbits[ ] for finding the total count of set bits present in the range [l,r] i.e preSetbits[r] - preSetbits[l-1]
   
• We will follow the same method for answering each query.

Code

//C++ implementation of the above-mentioned approach #include<bits/stdc++.h> using namespace std; void queries(vector<int> arr,vector<vector<int>> query) { int n=arr.size(); vector<int> preSetbits(n,0); preSetbits[0]=__builtin_popcount(arr[0]); // storing count of set bits upto ith index for(int i=1;i<n;i++) { preSetbits[i]=preSetbits[i-1]+__builtin_popcount(arr[i]); } for(int i=0;i<query.size();i++) { int l=query[i][0]; int r=query[i][1]; if(l==0) { cout<<"for query ("<<l<<","<<r<<") : "<<preSetbits[r]<<endl; } else { cout<<"for query ("<<l<<","<<r<<") : "<<preSetbits[r]-preSetbits[l-1]<<endl; } } } //driver code int main() { vector<int> arr{1, 5, 3, 8, 7, 2}; vector<vector<int>> query{{0, 1}, {3, 3}, {2, 5}}; queries(arr,query); } You can also try this code with Online C++ Compiler Run Code

Output

Also see, Euclid GCD Algorithm

Complexity analysis

In the worst-case time, the complexity of the above approach is O(q + n*logk) ≅ O(q + n) where q is the number of queries, n is the size of the array and k is the max number of bits present in an element of the array. So, logk is a constant as max value of k is 32 for an integer.

Space complexity is O(n) as we are using extra space.

FAQs

1. What is  __builtin_popcount( ) ?
   It is one of the built-in functions of the GCC compiler. This function takes an integer and returns the number of set bits present in the integer.
    
2. Why is the vector in C++ called dynamic array?
   Vector can resize itself when an element is inserted or deleted from the vector.

Key Takeaways

This article covered how to count set bits in index range [L, R] in the given array for Q queries.

Recommended reading:

• Introduction to JQuery

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.

Check out this problem - Maximum Product Subarray

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!