text: Count of elements which are power of 2 in a given range subarray for Q queries | C ++ implementation to find elements that are a power of two ; prefix [ i ] is going to store the number of elements which are a power of two till i ( including i ) . ; Function to find the maximum range whose sum is divisible by M . ; Calculate the prefix sum ; Function to return the number of elements which are a power of two in a subarray ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 10000 ; int prefix [ MAX + 1 ] ; bool isPowerOfTwo ( int x ) { if ( x && ( ! ( x & ( x - 1 ) ) ) ) return true ; return false ; } void computePrefix ( int n , int a [ ] ) { if ( isPowerOfTwo ( a [ 0 ] ) ) prefix [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { prefix [ i ] = prefix [ i - 1 ] ; if ( isPowerOfTwo ( a [ i ] ) ) prefix [ i ] ++ ; } } int query ( int L , int R ) { return prefix [ R ] - prefix [ L - 1 ] ; } int main ( ) { int A [ ] = { 3 , 8 , 5 , 2 , 5 , 10 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int Q = 2 ; computePrefix ( N , A ) ; cout << query ( 0 , 4 ) << " STRNEWLINE " ; cout << query ( 3 , 5 ) << " STRNEWLINE " ; return 0 ; }