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 ; Driver Code ; Given array ; Size of the array ; Given queries ; Size of queries array
def check ( x ) : NEW_LINE INDENT if ( ( ( x ) & ( x - 1 ) ) == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT def query ( l , r , pre ) : NEW_LINE INDENT if ( l == 0 ) : NEW_LINE INDENT return pre [ r ] NEW_LINE DEDENT else : NEW_LINE INDENT return pre [ r ] - pre [ l - 1 ] NEW_LINE DEDENT DEDENT def countInRange ( arr , N , queries , Q ) : NEW_LINE INDENT pre = [ 0 ] * N NEW_LINE pre [ 0 ] = check ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT pre [ i ] = pre [ i - 1 ] + check ( arr [ i ] ) NEW_LINE DEDENT c = 0 NEW_LINE while ( Q > 0 ) : NEW_LINE INDENT l = queries [ 0 ] NEW_LINE r = queries [ 1 ] NEW_LINE c += 1 NEW_LINE print ( query ( l , r , pre ) , end = " ▁ " ) NEW_LINE Q -= 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 12 , 11 , 16 , 8 , 2 , 5 , 1 , 3 , 256 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE queries = [ [ 0 , 9 ] , [ 4 , 9 ] ] NEW_LINE Q = len ( queries ) NEW_LINE countInRange ( arr , N , queries , Q ) NEW_LINE DEDENT