XOR of all possible pairwise sum from two given Arrays | Python3 program to implement the above approach ; 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
from bisect import bisect , bisect_left , bisect_right NEW_LINE def XorSum ( A , B , N ) : NEW_LINE INDENT maxBit = 29 NEW_LINE ans = 0 NEW_LINE for k in range ( maxBit ) : NEW_LINE INDENT C = [ 0 ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT C [ i ] = B [ i ] % ( 1 << ( k + 1 ) ) NEW_LINE DEDENT C = sorted ( C ) NEW_LINE count = 0 NEW_LINE l , r = 0 , 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT x = A [ i ] % ( 1 << ( k + 1 ) ) NEW_LINE l = bisect_left ( C , ( 1 << k ) - x ) NEW_LINE r = bisect_left ( C , ( 1 << k ) * 2 - x ) NEW_LINE count += ( r - l ) NEW_LINE l = bisect_left ( C , ( 1 << k ) * 3 - x ) NEW_LINE r = bisect_left ( C , ( 1 << k ) * 4 - x ) NEW_LINE count += ( r - l ) NEW_LINE DEDENT if ( count & 1 ) : NEW_LINE INDENT ans += ( 1 << k ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 4 , 6 , 0 , 0 , 3 , 3 ] NEW_LINE B = [ 0 , 5 , 6 , 5 , 0 , 3 ] NEW_LINE N = len ( A ) NEW_LINE print ( XorSum ( A , B , N ) ) NEW_LINE DEDENT