Number whose sum of XOR with given array range is maximum | Python3 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
import math NEW_LINE one = [ [ 0 for x in range ( 32 ) ] for y in range ( 100001 ) ] NEW_LINE MAX = 2147483647 NEW_LINE def make_prefix ( A , n ) : NEW_LINE INDENT global one , MAX NEW_LINE for j in range ( 0 , 32 ) : NEW_LINE INDENT one [ 0 ] [ j ] = 0 NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT a = A [ i - 1 ] NEW_LINE for j in range ( 0 , 32 ) : NEW_LINE INDENT x = int ( math . pow ( 2 , j ) ) NEW_LINE if ( a & x ) : NEW_LINE INDENT one [ i ] [ j ] = 1 + one [ i - 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT one [ i ] [ j ] = one [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def Solve ( L , R ) : NEW_LINE INDENT global one , MAX NEW_LINE l = L NEW_LINE r = R NEW_LINE tot_bits = r - l + 1 NEW_LINE X = MAX NEW_LINE for i in range ( 0 , 31 ) : NEW_LINE INDENT x = one [ r ] [ i ] - one [ l - 1 ] [ i ] NEW_LINE if ( x >= ( tot_bits - x ) ) : NEW_LINE INDENT ith_bit = pow ( 2 , i ) NEW_LINE X = X ^ ith_bit NEW_LINE DEDENT DEDENT return X NEW_LINE DEDENT n = 5 NEW_LINE q = 3 NEW_LINE A = [ 210 , 11 , 48 , 22 , 133 ] NEW_LINE L = [ 1 , 4 , 2 ] NEW_LINE R = [ 3 , 14 , 4 ] NEW_LINE make_prefix ( A , n ) NEW_LINE for j in range ( 0 , q ) : NEW_LINE INDENT print ( Solve ( L [ j ] , R [ j ] ) , end = " " ) NEW_LINE DEDENT