Count of elements which are power of 2 in a given range subarray for Q queries | Javascript 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
let MAX = 10000 ; let prefix = Array . from ( { length : MAX + 1 } , ( _ , i ) => 0 ) ; function isPowerOfTwo ( x ) { if ( x != 0 && ( ( x & ( x - 1 ) ) == 0 ) ) return true ; return false ; } function computePrefix ( n , a ) { if ( isPowerOfTwo ( a [ 0 ] ) ) prefix [ 0 ] = 1 ; for ( let i = 1 ; i < n ; i ++ ) { prefix [ i ] = prefix [ i - 1 ] ; if ( isPowerOfTwo ( a [ i ] ) ) prefix [ i ] ++ ; } } function query ( L , R ) { if ( L == 0 ) return prefix [ R ] ; return prefix [ R ] - prefix [ L - 1 ] ; } let A = [ 3 , 8 , 5 , 2 , 5 , 10 ] ; let N = A . length ; computePrefix ( N , A ) ; document . write ( query ( 0 , 4 ) + " " ) ; document . write ( query ( 3 , 5 ) ) ;