XOR of all possible pairwise sum from two given Arrays | Java Program to implement the above approach ; 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
import java . util . * ; class GFG { static int lower_bound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } static int XorSum ( int A [ ] , int B [ ] , int N ) { final int maxBit = 29 ; int ans = 0 ; for ( int k = 0 ; k < maxBit ; k ++ ) { int [ ] C = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { C [ i ] = B [ i ] % ( 1 << ( k + 1 ) ) ; } Arrays . sort ( C ) ; long count = 0 ; long l , r ; for ( int i = 0 ; i < N ; i ++ ) { int 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 ; } public static void main ( String [ ] args ) { int A [ ] = { 4 , 6 , 0 , 0 , 3 , 3 } ; int B [ ] = { 0 , 5 , 6 , 5 , 0 , 3 } ; int N = A . length ; System . out . print ( XorSum ( A , B , N ) + "NEW_LINE"); } }