Problem

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 theXOR sum of the aforementioned list.

Examples

Example 1

1
2
3
4

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

1
2
3

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

Solution

Method 1 – Bitwise Property (Distributive Law)

Intuition

The XOR sum of all (arr1[i] & arr2[j]) pairs can be computed efficiently using the property:

  • (a & b) ^ (a & c) = a & (b ^ c)
  • So, XORing all (arr1[i] & arr2[j]) for all i, j is the same as (XOR of arr1) & (XOR of arr2).

Approach

  1. Compute the XOR of all elements in arr1 (call it x1).
  2. Compute the XOR of all elements in arr2 (call it x2).
  3. Return x1 & x2.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int xorSum(vector<int>& arr1, vector<int>& arr2) {
        int x1 = 0, x2 = 0;
        for (int a : arr1) x1 ^= a;
        for (int b : arr2) x2 ^= b;
        return x1 & x2;
    }
};
1
2
3
4
5
6

func xorSum(arr1, arr2 []int) int {
    x1, x2 := 0, 0
    for _, a := range arr1 { x1 ^= a }
    for _, b := range arr2 { x2 ^= b }
    return x1 & x2
}
1
2
3
4
5
6
7
8

class Solution {
    public int xorSum(int[] arr1, int[] arr2) {
        int x1 = 0, x2 = 0;
        for (int a : arr1) x1 ^= a;
        for (int b : arr2) x2 ^= b;
        return x1 & x2;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun xorSum(arr1: IntArray, arr2: IntArray): Int {
        var x1 = 0; var x2 = 0
        for (a in arr1) x1 = x1 xor a
        for (b in arr2) x2 = x2 xor b
        return x1 and x2
    }
}
1
2
3
4
5
6
7

class Solution:
    def xorSum(self, arr1: list[int], arr2: list[int]) -> int:
        x1 = 0
        for a in arr1: x1 ^= a
        x2 = 0
        for b in arr2: x2 ^= b
        return x1 & x2
1
2
3
4
5
6
7

impl Solution {
    pub fn xor_sum(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
        let x1 = arr1.iter().fold(0, |acc, &a| acc ^ a);
        let x2 = arr2.iter().fold(0, |acc, &b| acc ^ b);
        x1 & x2
    }
}
1
2
3
4
5
6
7
8

class Solution {
    xorSum(arr1: number[], arr2: number[]): number {
        let x1 = 0, x2 = 0;
        for (const a of arr1) x1 ^= a;
        for (const b of arr2) x2 ^= b;
        return x1 & x2;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n and m are the lengths of arr1 and arr2, since we scan both arrays once.
  • 🧺 Space complexity: O(1), only a few variables are used.