Number whose sum of XOR with given array range is maximum | Javascript program to find smallest integer X such that sum of its XOR with range is maximum . ; Function to make prefix array which counts 1 's of each bit up to that number ; Making a prefix array which sums number of 1 's up to that position ; If j - th bit of a number is set then add one to previously counted 1 's ; Function to find X ; Initially taking maximum value all bits 1 ; Iterating over each bit ; get 1 ' s ▁ at ▁ ith ▁ bit ▁ between ▁ the ▁ ▁ range ▁ L - R ▁ by ▁ subtracting ▁ 1' s till Rth number - 1 's till L-1th number ; If 1 ' s ▁ are ▁ more ▁ than ▁ or ▁ equal ▁ to ▁ 0' s then unset the ith bit from answer ; Set ith bit to 0 by doing Xor with 1 ; Driver program Taking inputs
const MAX = 2147483647 ; let one = new Array ( 100001 ) ; for ( let i = 0 ; i < 100001 ; i ++ ) one [ i ] = new Array ( 32 ) ; function make_prefix ( A , n ) { for ( let j = 0 ; j < 32 ; j ++ ) one [ 0 ] [ j ] = 0 ; for ( let i = 1 ; i <= n ; i ++ ) { let a = A [ i - 1 ] ; for ( let j = 0 ; j < 32 ; j ++ ) { let x = Math . pow ( 2 , j ) ; if ( a & x ) one [ i ] [ j ] = 1 + one [ i - 1 ] [ j ] ; else one [ i ] [ j ] = one [ i - 1 ] [ j ] ; } } } function Solve ( L , R ) { let l = L , r = R ; let tot_bits = r - l + 1 ; let X = MAX ; for ( let i = 0 ; i < 31 ; i ++ ) { let x = one [ r ] [ i ] - one [ l - 1 ] [ i ] ; if ( x >= tot_bits - x ) { let ith_bit = Math . pow ( 2 , i ) ; X = X ^ ith_bit ; } } return X ; } let n = 5 , q = 3 ; let A = [ 210 , 11 , 48 , 22 , 133 ] ; let L = [ 1 , 4 , 2 ] , R = [ 3 , 14 , 4 ] ; make_prefix ( A , n ) ; for ( let j = 0 ; j < q ; j ++ ) document . write ( Solve ( L [ j ] , R [ j ] ) + " " ) ;