Queries to check whether bitwise AND of a subarray is even or odd | Python implementation of the approach ; Function to precompute the count of even and odd numbers ; If the current element is odd then put 1 at odd [ i ] ; If the current element is even then put 1 at even [ i ] ; Taking the prefix sums of these two arrays so we can get the count of even and odd numbers in a range [ L , R ] in O ( 1 ) ; Function that returns True if the bitwise AND of the subarray a [ L ... R ] is odd ; cnt will store the count of odd numbers in the range [ L , R ] ; Check if all the numbers in the range are odd or not ; Function to perform the queries ; Perform queries ; Driver code ; Queries
MAXN = 1000005 ; NEW_LINE even = [ 0 ] * MAXN ; NEW_LINE odd = [ 0 ] * MAXN ; NEW_LINE def precompute ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] % 2 == 1 ) : NEW_LINE INDENT odd [ i ] = 1 ; NEW_LINE DEDENT if ( arr [ i ] % 2 == 0 ) : NEW_LINE INDENT even [ i ] = 1 ; NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT even [ i ] = even [ i ] + even [ i - 1 ] ; NEW_LINE odd [ i ] = odd [ i ] + odd [ i - 1 ] ; NEW_LINE DEDENT DEDENT def isOdd ( L , R ) : NEW_LINE INDENT cnt = odd [ R ] ; NEW_LINE if ( L > 0 ) : NEW_LINE INDENT cnt -= odd [ L - 1 ] ; NEW_LINE DEDENT if ( cnt == R - L + 1 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT return False ; NEW_LINE DEDENT def performQueries ( a , n , q , m ) : NEW_LINE INDENT precompute ( a , n ) ; NEW_LINE for i in range ( m ) : NEW_LINE INDENT L = q [ i ] [ 0 ] ; NEW_LINE R = q [ i ] [ 1 ] ; NEW_LINE if ( isOdd ( L , R ) ) : NEW_LINE INDENT print ( " Odd " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Even " ) ; NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 2 , 1 , 5 , 7 , 6 , 8 , 9 ] ; NEW_LINE n = len ( a ) ; NEW_LINE q = [ [ 0 , 2 ] , [ 1 , 2 ] , [ 2 , 3 ] , [ 3 , 6 ] ] ; NEW_LINE m = len ( q ) ; NEW_LINE performQueries ( a , n , q , m ) ; NEW_LINE DEDENT