XOR of all possible pairwise sum from two given Arrays | Lower bound ; Function to calculate the XOR of the sum of every pair ; Stores the maximum bit ; Look for all the k - th bit ; Stores the modulo of elements B [ ] with ( 2 ^ ( k + 1 ) ) ; Calculate modulo of array B [ ] with ( 2 ^ ( k + 1 ) ) ; Sort the array C [ ] ; Stores the total number whose k - th bit is set ; Calculate and store the modulo of array A [ ] with ( 2 ^ ( k + 1 ) ) ; Lower bound to count the number of elements having k - th bit in the range ( 2 ^ k - x , 2 * 2 ^ ( k ) - x ) ; Add total number i . e ( r - l ) whose k - th bit is one ; Lower bound to count the number of elements having k - th bit in range ( 3 * 2 ^ k - x , 4 * 2 ^ ( k ) - x ) ; If count is even , Xor of k - th bit becomes zero , no need to add to the answer . If count is odd , only then , add to the final answer ; Return answer ; Driver code ; Function call
function lower_bound ( a , low , high , element ) { while ( low < high ) { let middle = low + Math . floor ( ( high - low ) / 2 ) ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } function XorSum ( A , B , N ) { let maxBit = 29 ; let ans = 0 ; for ( let k = 0 ; k < maxBit ; k ++ ) { let C = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { C [ i ] = B [ i ] % ( 1 << ( k + 1 ) ) ; } C . sort ( function ( x , y ) { return x - y ; } ) ; let count = 0 ; let l , r ; for ( let i = 0 ; i < N ; i ++ ) { let x = A [ i ] % ( 1 << ( k + 1 ) ) ; l = lower_bound ( C , 0 , N , ( 1 << k ) - x ) ; r = lower_bound ( C , 0 , N , ( 1 << k ) * 2 - x ) ; count += ( r - l ) ; l = lower_bound ( C , 0 , N , ( 1 << k ) * 3 - x ) ; r = lower_bound ( C , 0 , N , ( 1 << k ) * 4 - x ) ; count += ( r - l ) ; } if ( ( count & 1 ) != 0 ) ans += ( 1 << k ) ; } return ans ; } let A = [ 4 , 6 , 0 , 0 , 3 , 3 ] ; let B = [ 0 , 5 , 6 , 5 , 0 , 3 ] ; let N = A . length ; document . write ( XorSum ( A , B , N ) + " " ) ;