Find XOR Sum of All Pairs Bitwise AND (IMPORTAN)

question link -> https://leetcode.com/problems/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
Explanation: The list = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1].
The XOR sum = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0.

* Example 2:
Input: arr1 = [12], arr2 = [4]
Output: 4
Explanation: The list = [12 AND 4] = [4]. The XOR sum = 4.


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

APPROACH 1

MY THOUGHTS ON THIS APPROACH-
See, you are pairing up elements right. But, BUT, first you AND them. See AND needs even number of bits set, i.e. 1 & 1 = 1, otherwise if you have odd number of bits set, then this results in 0 as 1 & 0 = 0. So, what you do, you can see highest number in array can be 10^9, so 2^30 would suffice. So, iterate from 0 to 30 bits, and check how many elements in arr1 and arr2 have i-bit set, because this is what we are concerned with. Now you have two variables cnt1, cnt2 representing number of elements having ith bit set in arr1 and same goes for arr2. Multiplying these two cnt1,cnt2 would give us the number of set bits we can get for ith bit. Multiplying because we are pairing elements. Now check if the product of cnt1,cnt2 is even or odd. If even, this means when you will XOR these all pairs, then ith bit will become zero. Because there are even number of set bits , and 1 ^ 1 = 0, BUT if it is odd, this means 1 set bit will remain. And this will come in our answer during the XOR process. So, set this ith bit in our res variable

class Solution {
public:
    long long int count(vector<int> &arr, int bit){ // count number of elements in arr whose "bit" is set. Checking how many elements in arr are having given "bit" set.
        long long int cnt=0;
        for(auto x: arr){
            if((x & (1 << bit))){  // bit is on
                cnt++;
            }
        }
        return cnt;
    }

    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        // 2^30 is the smallest power of 2 that results in a number>=10^9
        int res=0;
        for(int bit=0;bit<=30;bit++){
            long long int cnt1=count(arr1,bit);
            long long int cnt2=count(arr2,bit);
            if((cnt1*cnt2)%2!=0){ // cnt1*cnt2 represent number of bits that are set after the AND operation. Now, during XOR, we know 1 ^ 1 = 0, so even counts of 1 will cancel each other out, for example, 1 ^ 1 ^ 1 ^ 1 = 0, but if there are odd count of 1, there still will be 1 set bit remaining. For example, 1 ^ 1 ^ 1 = 0 ^ 1 = 1. So, you see, we set this bit in res because it will always be present here
                res=res | (1 << bit);
            }
        }
        return res;
    }
};


---------------------------------------------------------------------------------------------------------------------------------------

APPROACH 2-

MY THOUGHTS ON THIS APPROACH-
(a & b) ^ (a & c) can be simplified to (a & (b ^ c))

The steps to simplify the expression.

1) First, we use the distributive property of the bitwise AND operator:
(a & b) ^ (a & c) = a & b ^ a & c

2) Next, we use the associative property of the bitwise XOR operator:
a & b ^ a & c = a & (b ^ a) & c

3) We use the identity property of the bitwise XOR operator:
a & (b ^ a) & c = a & (a ^ b) & c = a & (a ^ b) ^ a & c

4) We use the identity property of the bitwise AND operator:
a & (a ^ b) ^ a & c = a & (a ^ b) ^ (a & c)

5) We use the distributive property of the bitwise AND operator:
a & (a ^ b) ^ (a & c) = a & (a ^ b) ^ (a & c)

6) We use the identity property of the bitwise AND operator:
(a & a) ^ b & c = a & (b ^ c)



class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        // (a & b) ^ (a & c) can be simplified to (a & (b ^ c))
        int totalXOR=0;
        for(auto x: arr2){
            totalXOR^=x;
        }
        int res=0;
        for(auto x: arr1){
            int X=x & totalXOR;
            res=res ^ X;
        }
        return res;
    }
};