Queries on XOR of greatest odd divisor of the range | Java code 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 ; Driven Program
import java . io . * ; class GFG { static void prefixXOR ( int arr [ ] , int preXOR [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) { while ( arr [ i ] % 2 != 1 ) arr [ i ] /= 2 ; preXOR [ i ] = arr [ i ] ; } for ( int i = 1 ; i < n ; i ++ ) preXOR [ i ] = preXOR [ i - 1 ] ^ preXOR [ i ] ; } static int query ( int preXOR [ ] , int l , int r ) { if ( l == 0 ) return preXOR [ r ] ; else return preXOR [ r ] ^ preXOR [ l - 1 ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 4 , 5 } ; int n = arr . length ; int preXOR [ ] = new int [ n ] ; prefixXOR ( arr , preXOR , n ) ; System . out . println ( query ( preXOR , 0 , 2 ) ) ; System . out . println ( query ( preXOR , 1 , 2 ) ) ; } }