Find XOR Sum of All Pairs Bitwise AND

Problem

Given two integer arrays arr1 and arr2, form every pair (a, b) with a from arr1 and b from arr2, compute a AND b for each pair, and XOR all the results together.

Return this single integer.

Intuition

The brute force computes n * m AND values and XORs them — O(n * m). For n, m ≤ 10^5 that is 10^{10} operations, far too many.

Work bit-by-bit. At bit position k:

• (a AND b) has bit k set iff both a and b have bit k set.
• In the XOR of all pairs, bit k is set iff an odd number of pairs have bit k in their AND. That count is c1 * c2, where c1 is how many elements of arr1 have bit k set and c2 the same for arr2.
• c1 * c2 is odd iff both c1 and c2 are odd.
• c1 is odd iff the XOR of all arr1 elements has bit k set. (XOR toggles once per 1-bit, and its parity is the count mod 2.)

Therefore: the answer is simply (XOR of arr1) AND (XOR of arr2).

Approach

impl Solution {
    pub fn get_xor_sum(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
        let mut result = 0;
        for &a in &arr1 {
            for &b in &arr2 {
                result ^= a & b;
            }
        }
        result
    }
}

function getXORSum(arr1: number[], arr2: number[]): number {
  let result = 0;
  for (const a of arr1) {
    for (const b of arr2) {
      result ^= a & b;
    }
  }
  return result;
}

impl Solution {
    pub fn get_xor_sum(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
        let xor1: i32 = arr1.iter().fold(0, |acc, &x| acc ^ x);
        let xor2: i32 = arr2.iter().fold(0, |acc, &x| acc ^ x);
        xor1 & xor2
    }
}

function getXORSum(arr1: number[], arr2: number[]): number {
  let xor1 = 0;
  for (const a of arr1) xor1 ^= a;
  let xor2 = 0;
  for (const b of arr2) xor2 ^= b;
  return xor1 & xor2;
}

Trace

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

Edge cases

• Single element arrays — degenerates to arr1[0] AND arr2[0].
• All zeros — XOR of anything with 0 stays 0; result is 0.
• One array all same value — XOR is 0 if even count, value if odd count; AND with other XOR accordingly.
• Large values (up to 10^9) — safe within 32-bit signed int.

Takeaway

Think bit-by-bit. When a problem combines XOR (parity-sensitive) with AND (bitwise filter), decompose into per-bit analysis. The parity argument — "count of set bits in this position across all pairs" collapses to the XOR of individual arrays — turns a quadratic problem into a linear one.

This "distributive" reduction shows up in hardware design (combining bus signals), coding theory (syndrome decoding), and competitive programming whenever you see "XOR of all (f AND g)" patterns.