Queries to count array elements from a given range having a single set bit | JAVA 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 ; A Pair class for handling queries in JAVA As , there is no in - built function of Tuple ; Driver code ; Given array ; Size of the array ; Given queries ; Size of queries array
import java . util . * ; import java . io . * ; import java . math . * ; public class GFG { static int check ( int x ) { if ( ( ( x ) & ( x - 1 ) ) == 0 ) return 1 ; return 0 ; } static int query ( int l , int r , int [ ] pre ) { if ( l == 0 ) return pre [ r ] ; else return pre [ r ] - pre [ l - 1 ] ; } static void countInRange ( int [ ] arr , int N , ArrayList < Pair > queries , int Q ) { int [ ] pre = new int [ N ] ; pre [ 0 ] = check ( arr [ 0 ] ) ; for ( int i = 1 ; i < N ; i ++ ) { pre [ i ] = pre [ i - 1 ] + check ( arr [ i ] ) ; } int c = 0 ; int q = 0 ; while ( q < Q ) { int l = queries . get ( q ) . item1 ; int r = queries . get ( q ) . item2 ; c ++ ; q ++ ; System . out . print ( query ( l , r , pre ) + " ▁ " ) ; } } static class Pair { int item1 , item2 ; Pair ( int item1 , int item2 ) { this . item1 = item1 ; this . item2 = item2 ; } } public static void main ( String args [ ] ) { int [ ] arr = { 12 , 11 , 16 , 8 , 2 , 5 , 1 , 3 , 256 , 1 } ; int N = arr . length ; ArrayList < Pair > queries = new ArrayList < Pair > ( ) ; queries . add ( new Pair ( 4 , 9 ) ) ; queries . add ( new Pair ( 0 , 9 ) ) ; int Q = queries . size ( ) ; countInRange ( arr , N , queries , Q ) ; } }