Number whose sum of XOR with given array range is maximum | PHP 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 Code
< ? php $ one = array ( ) ; $ MAX = 2147483647 ; function make_prefix ( $ A , $ n ) { global $ one , $ MAX ; for ( $ j = 0 ; $ j < 32 ; $ j ++ ) $ one [ 0 ] [ $ j ] = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { $ a = $ A [ $ i - 1 ] ; for ( $ j = 0 ; $ j < 32 ; $ j ++ ) { $ x = 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 ) { global $ one , $ MAX ; $ l = $ L ; $ r = $ R ; $ tot_bits = $ r - $ l + 1 ; $ X = $ MAX ; for ( $ i = 0 ; $ i < 31 ; $ i ++ ) { $ x = $ one [ $ r ] [ $ i ] - $ one [ $ l - 1 ] [ $ i ] ; if ( $ x >= ( $ tot_bits - $ x ) ) { $ ith_bit = pow ( 2 , $ i ) ; $ X = $ X ^ $ ith_bit ; } } return $ X ; } $ n = 5 ; $ q = 3 ; $ A = [ 210 , 11 , 48 , 22 , 133 ] ; $ L = [ 1 , 4 , 2 ] ; $ R = [ 3 , 14 , 4 ] ; make_prefix ( $ A , $ n ) ; for ( $ j = 0 ; $ j < $ q ; $ j ++ ) echo ( Solve ( $ L [ $ j ] , $ R [ $ j ] ) . " STRNEWLINE " ) ; ? >