Queries to count array elements from a given range having a single set bit | C ++ program for the above approach ; Function to check whether only one bit is set or not ; Function to perform Range - query ; Function to count array elements with a single set bit for each range in a query ; Initialize array for Prefix sum ; Driver Code ; Given array ; Size of the array ; Given queries ; Size of queries array
#include <bits/stdc++.h> NEW_LINE using namespace std ; int check ( int x ) { if ( ( ( x ) & ( x - 1 ) ) == 0 ) return 1 ; return 0 ; } int query ( int l , int r , int pre [ ] ) { if ( l == 0 ) return pre [ r ] ; else return pre [ r ] - pre [ l - 1 ] ; } void countInRange ( int arr [ ] , int N , vector < pair < int , int > > queries , int Q ) { int pre [ N ] = { 0 } ; pre [ 0 ] = check ( arr [ 0 ] ) ; for ( int i = 1 ; i < N ; i ++ ) { pre [ i ] = pre [ i - 1 ] + check ( arr [ i ] ) ; } int c = 0 ; while ( Q -- ) { int l = queries . first ; int r = queries . second ; c ++ ; cout << query ( l , r , pre ) << ' ▁ ' ; } } int main ( ) { int arr [ ] = { 12 , 11 , 16 , 8 , 2 , 5 , 1 , 3 , 256 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; vector < pair < int , int > > queries = { { 0 , 9 } , { 4 , 9 } } ; int Q = queries . size ( ) ; countInRange ( arr , N , queries , Q ) ; return 0 ; }