Queries on XOR of greatest odd divisor of the range | Precompute the prefix XOR of greatest odd divisor ; Finding the Greatest Odd divisor ; Finding prefix XOR ; Return XOR of the range ; Driver Code
def prefixXOR ( arr , preXOR , n ) : NEW_LINE INDENT for i in range ( 0 , n , 1 ) : NEW_LINE INDENT while ( arr [ i ] % 2 != 1 ) : NEW_LINE INDENT arr [ i ] = int ( arr [ i ] / 2 ) NEW_LINE DEDENT preXOR [ i ] = arr [ i ] NEW_LINE DEDENT for i in range ( 1 , n , 1 ) : NEW_LINE INDENT preXOR [ i ] = preXOR [ i - 1 ] ^ preXOR [ i ] NEW_LINE DEDENT DEDENT def query ( preXOR , l , r ) : NEW_LINE INDENT if ( l == 0 ) : NEW_LINE INDENT return preXOR [ r ] NEW_LINE DEDENT else : NEW_LINE INDENT return preXOR [ r ] ^ preXOR [ l - 1 ] NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE preXOR = [ 0 for i in range ( n ) ] NEW_LINE prefixXOR ( arr , preXOR , n ) NEW_LINE print ( query ( preXOR , 0 , 2 ) ) NEW_LINE print ( query ( preXOR , 1 , 2 ) ) NEW_LINE DEDENT