Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
4.
Code
5.
Complexity analysis
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Malay Gain
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Counting set bits in a number is not a very hard task. It can be computed easily using the concept of bit manipulation. Here we will be discussing how to count set bits from a given range of values of an array. Here our main objective is to perform such queries on a given array efficiently.

 

 Let’s go through the problem statement. Then we will see the solution approach. 

 

Problem statement

You are given an array of integers. You are given some queries of ranges. For each query, you need to find the total count of set bits considering all integers of the given range.

 

Input

arr[ ]={1, 5, 3, 8, 7, 2}
   query[ ]={{0, 1}, {3, 3}, {2, 5}}

Output

for query (0,1) : 3
for query (3,3) : 1
for query (2,5) : 7

 

Explanation

arr[ ]={1, 5, 3, 8, 7, 2}
   Idx: 0  1  2  3  4  5

1=(1)2
5=(101)2
3=(11)2
8=(1000)2
7=(111)2
2=(10)2

So, for range [0,1]  count of set bits= 1+2=3;
       for range [3,3]  count of set bits = 1;
       for range [2,5]  count of set bits= 2+1+3+1=7

 

Note: Please try to solve the problem first and then see the solution below.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
}

 

Output

for query (0,1) : 3

for query (3,3) : 1

for query (2,5) : 7

 

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:

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!

 

Previous article
Convert given binary to its equivalent ASCII character string
Next article
Count Total Set Bits in an Array
Live masterclass