Queries to count array elements from a given range having a single set bit | 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 ; Given array ; Size of the array ; Given queries ; Size of queries array
function check ( x ) { if ( ( ( x ) & ( x - 1 ) ) == 0 ) return 1 ; return 0 ; } function query ( l , r , pre ) { if ( l == 0 ) return pre [ r ] ; else return pre [ r ] - pre [ l - 1 ] ; } function countInRange ( arr , N , queries , Q ) { var pre = Array ( N ) . fill ( 0 ) ; pre [ 0 ] = check ( arr [ 0 ] ) ; for ( var i = 1 ; i < N ; i ++ ) { pre [ i ] = pre [ i - 1 ] + check ( arr [ i ] ) ; } var c = 0 ; while ( Q -- ) { var l = queries [ 0 ] ; var r = queries [ 1 ] ; c ++ ; document . write ( query ( l , r , pre ) + ' ' ) ; } } var arr = [ 12 , 11 , 16 , 8 , 2 , 5 , 1 , 3 , 256 , 1 ] ; var N = arr . length ; var queries = [ [ 0 , 9 ] , [ 4 , 9 ] ] ; var Q = queries . length ; countInRange ( arr , N , queries , Q ) ;