Count set bits in index range [L, R] in given Array for Q queries
Given an array arr[] containing N integers and an array queries[] containing Q queries in the form of {L, R}, the task is to count the total number of set bits from L to R in array arr for each query.
Example:
Input: arr[]={1, 2, 3, 4, 5, 6}, queries[]={{0, 2}, {1, 1}, {3, 5}}
Output:
4
2
5
Explanation:
Query 1 (0, 2): Elements {1, 2, 3} have set bits {1, 1, 2} respectively. So sum=1+1+2=4
Query 1 (1, 1): Element {2} have set bit {1}. So sum=1
Query 1 (3, 5): Elements {4, 5, 6} have set bits {1, 2, 2} respectively. So sum=1+2+2=5Input: arr[]={2, 4, 3, 5, 6}, queries[]={{0, 1}, {2, 4}}
Output:
2
6
Approach: To solve this question, follow the below steps:
- Create a vector, say onBits, in which each ith element will represent the number of set bits from arr[0] to arr[i].
- Run a loop from i=0 to i<N, and on each iteration, find the number of set bits in arr[i], say bits and make onBits[i]=onBits[i-1] + bits.
- Now traverse the array queries and for each query {L, R}, the number of set bits from L to R is onBits[R]-onBits[L-1].
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the number // of set bits from L to R int setBitsinLtoR( int L, int R, vector< int >& onBits) { if (L == 0) { return onBits[R]; } return onBits[R] - onBits[L - 1]; } // Function to find the number // of set bits for Q queries void totalSetBits(vector< int >& arr, vector<pair< int , int > >& queries) { int N = arr.size(); vector< int > onBits(N, 0); onBits[0] = __builtin_popcount(arr[0]); for ( int i = 1; i < N; ++i) { onBits[i] = onBits[i - 1] + __builtin_popcount(arr[i]); } // Finding for Q queries for ( auto x : queries) { int L = x.first; int R = x.second; cout << setBitsinLtoR(L, R, onBits) << endl; } } // Driver Code int main() { vector< int > arr = { 1, 2, 3, 4, 5, 6 }; vector<pair< int , int > > queries = { { 0, 2 }, { 1, 1 }, { 3, 5 } }; totalSetBits(arr, queries); } |
Java
// Java code for the above approach import java.util.*; class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to return the number // of set bits from L to R static int setBitsinLtoR( int L, int R, int []onBits) { if (L == 0 ) { return onBits[R]; } return onBits[R] - onBits[L - 1 ]; } // Function to find the number // of set bits for Q queries static void totalSetBits( int [] arr, pair[] queries) { int N = arr.length; int []onBits = new int [N]; onBits[ 0 ] = Integer.bitCount(arr[ 0 ]); for ( int i = 1 ; i < N; ++i) { onBits[i] = onBits[i - 1 ] + Integer.bitCount(arr[i]); } // Finding for Q queries for (pair x : queries) { int L = x.first; int R = x.second; System.out.print(setBitsinLtoR(L, R, onBits) + "\n" ); } } // Driver Code public static void main(String[] args) { int []arr = { 1 , 2 , 3 , 4 , 5 , 6 }; pair []queries = { new pair( 0 , 2 ), new pair( 1 , 1 ), new pair( 3 , 5 ) }; totalSetBits(arr, queries); } } // This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach def __builtin_popcount(n): count = 0 while (n): count + = n & 1 n >> = 1 return count # Function to return the number # of set bits from L to R def setBitsinLtoR(L, R, onBits): if (L = = 0 ): return onBits[R]; return onBits[R] - onBits[L - 1 ]; # Function to find the number # of set bits for Q queries def totalSetBits(arr, queries): N = len (arr); onBits = [ 0 ] * N onBits[ 0 ] = __builtin_popcount(arr[ 0 ]); for i in range ( 1 , N): onBits[i] = onBits[i - 1 ] + __builtin_popcount(arr[i]); # Finding for Q queries for x in queries: L = x[ 0 ]; R = x[ 1 ]; print (setBitsinLtoR(L, R, onBits)) # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 , 6 ]; queries = [ [ 0 , 2 ], [ 1 , 1 ], [ 3 , 5 ] ]; totalSetBits(arr, queries); # This code is contributed by gfgking |
C#
// C# code for the above approach using System; class GFG{ class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to return the number // of set bits from L to R static int setBitsinLtoR( int L, int R, int []onBits) { if (L == 0) { return onBits[R]; } return onBits[R] - onBits[L - 1]; } // Function to find the number // of set bits for Q queries static void totalSetBits( int [] arr, pair[] queries) { int N = arr.Length; int []onBits = new int [N]; onBits[0] = bitCount(arr[0]); for ( int i = 1; i < N; ++i) { onBits[i] = onBits[i - 1] + bitCount(arr[i]); } // Finding for Q queries foreach (pair x in queries) { int L = x.first; int R = x.second; Console.Write(setBitsinLtoR(L, R, onBits) + "\n" ); } } static int bitCount( int x) { int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5, 6 }; pair []queries = { new pair(0, 2), new pair(1, 1), new pair(3, 5) }; totalSetBits(arr, queries); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach function __builtin_popcount(x) { return ((x).toString(2).split( '' ). filter(x => x == '1' ).length); } // Function to return the number // of set bits from L to R function setBitsinLtoR(L, R, onBits) { if (L == 0) { return onBits[R]; } return onBits[R] - onBits[L - 1]; } // Function to find the number // of set bits for Q queries function totalSetBits(arr, queries) { let N = arr.length; let onBits = new Array(N).fill(0); onBits[0] = __builtin_popcount(arr[0]); for (let i = 1; i < N; ++i) { onBits[i] = onBits[i - 1] + __builtin_popcount(arr[i]); } // Finding for Q queries for (let x of queries) { let L = x[0]; let R = x[1]; document.write( setBitsinLtoR(L, R, onBits) + '<br>' ) } } // Driver Code let arr = [ 1, 2, 3, 4, 5, 6 ]; let queries = [ [ 0, 2 ], [ 1, 1 ], [ 3, 5 ] ]; totalSetBits(arr, queries); // This code is contributed by Potta Lokesh </script> |
4 1 5
Time Complexity: O(Q*N*logK), where N is the size of array arr, Q is the number of queries and K is the number of bits
Auxiliary Space: O(N)