1835. Find XOR Sum of All Pairs Bitwise AND

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element.

• For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4 and the XOR sum of [3] is equal to 3.

You are given two 0-indexed arrays arr1 and arr2 that consist only of non-negative integers.

Consider the list containing the result of arr1[i] AND arr2[j] (bitwise AND) for every (i, j) pair where 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of the aforementioned list.

Example: 1

Input: arr1 = [1,2,3], arr2 = [6,5]

Output: 0

Example: 2

Input: arr1 = [12], arr2 = [4]

Output: 4

Constraints:

• 1 <= arr1.length, arr2.length <= 10 ^ 5
• 0 <= arr1[i], arr2[j] <= 10 ^ 9

Thinking of an approach:

• Since we are required to make bitwise XOR and bitwise AND, we will split the numbers in the power of two. For eg: 5 can be broken as 2⁰ and 2².
• First we have to AND values from arr1 and arr2, so if we have a 2⁰ in arr1, and if arr2 doesn't have 2⁰, then even if we AND any value from this element of arr1 and any element of arr2, we won't be able to get 2⁰ in our final AND answer.
• And in vice versa, if we have K elements in arr2 having 2⁰ in them, then by doing bitwise AND of this element with any element of arr2 we will get 2⁰ K times.

Simplifying the above logic to code:

• Now what we will do is... split the numbers from arr2 in the forms of powers of 2 and store them in a map.
• Then for each power of 2 of elements in arr1, we will check their frequency from the map.
• This will enable us to know how many times the current power of 2 will be obtained in our result array (we will store these values in res).
• Finally xor all elements in res, and we will have our answer.

Full Code (Java): class Solution { public int getXORSum(int[] arr1, int[] arr2) { HashMap<Integer, Integer> map = new HashMap<>(); // storing the power of 2 // from each element in arr2 for(int num : arr2) { for(int i = 31; i >= 0; i--) { int pow = (1 << i) & num; if(pow != 0) { map.put(pow, map.getOrDefault(pow, 0) + 1); } } } // splitting the number in arr1 // in terms of powers of 2 // and checking their frequency from map // as mentioned above HashMap<Integer, Integer> res = new HashMap<>(); for(int num : arr1) { for(int i = 31; i >= 0; i--) { int pow = (1 << i) & num; if(pow != 0) { res.put(pow, res.getOrDefault(pow, 0) + map.getOrDefault(pow, 0)); } } } int xor = 0; // if any power of 2 // occurs even number of times // it will evaluate to 0 xor (think how ?) // so we will consider only powers of 2 // having odd frequency for(int key : res.keySet()) { if(res.get(key) % 2 != 0) { xor ^= key; } } return xor; } }